Fortgeschrittene Kombinatorik in Python: Binom(n,2)-Teilmengen von Binom(n,3)-Kombinationen ohne Wiederholung ⇐ Python

[Anonymous]

Ich habe eine Liste d_n von n ganzen Zahlen und die Ergebnisse Z_klm einer Funktion fun(dk, dl, dm) für alle binom(n, 3)-Kombinationen ohne Wiederholung (k, l, m) aus d_n-Indizes.
Nun für alle binom(n, 2)-Kombinationen ohne Wiederholungen (s, t) von d_n Indizes, ich muss die T_st Teilsummen von Z_klm nehmen, wobei (s, t) eine Teilmenge von (k, l, m) ist.
Hier ist ein Beispiel mit einem kleinen n.

Code: Select all

import numpy as np
from itertools import combinations
from scipy.special import binom

# generate random data
n = 5
d_n = np.random.randint(-30, 30, 5)

# define the function
def fun(dk, dl, dm):
return np.sign(dk - 2*dl + dm)

# calculate Z_klm and store (k,l,m) indices
klm = []
Z_klm = []
for k, l, m in combinations(range(n), 3):
Z_klm.append(fun(d_n[k], d_n[l], d_n[m]))
klm.append([k, l, m])

# calculate the partial sums T_st
st = {}
T_st = np.zeros(shape=int(binom(n, 2)))
for h, (s, t) in enumerate(combinations(range(n), 2)):
st.update({f"({s},{t})": []})
for i, _klm_ in enumerate(klm):
if s in _klm_ and t in _klm_:
T_st[h] += Z_klm[i]
st[f"({s},{t})"].append(_klm_)

T_st, st

Code: Select all

(array([ 1.,  1.,  2.,  2.,  1.,  1.,  1.,  1.,  1., -2.]),

{'(0,1)': [[0, 1, 2], [0, 1, 3], [0, 1, 4]],
'(0,2)': [[0, 1, 2], [0, 2, 3], [0, 2, 4]],
'(0,3)': [[0, 1, 3], [0, 2, 3], [0, 3, 4]],
'(0,4)': [[0, 1, 4], [0, 2, 4], [0, 3, 4]],
'(1,2)': [[0, 1, 2], [1, 2, 3], [1, 2, 4]],
'(1,3)': [[0, 1, 3], [1, 2, 3], [1, 3, 4]],
'(1,4)': [[0, 1, 4], [1, 2, 4], [1, 3, 4]],
'(2,3)': [[0, 2, 3], [1, 2, 3], [2, 3, 4]],
'(2,4)': [[0, 2, 4], [1, 2, 4], [2, 3, 4]],
'(3,4)': [[0, 3, 4], [1, 3, 4], [2, 3, 4]]})

Zum Beispiel ist T_{2,4} die Summe von Z_{0,2,4}, Z_{1,2,4} und Z_{2,3,4}.
Meine grobe Implementierung funktioniert nur, weil es hier nur sehr wenige Beobachtungen gibt. Aber im Falle realer Stichprobengrößen (kann normalerweise bis zu n = 1000 betragen) würde es ein Leben lang dauern, über das gesamte Binom(n,2) und das Binom(n,3) zu iterieren.
Irgendwelche Vorschläge, um es mit einem effizienten Algorithmus oder fortgeschritteneren Iterationstools zu beschleunigen?
P.S.: Ich muss nicht alle (k, l, m) und (s, t) Indizes; Ich habe es hier nur gemacht, um die Funktionsweise zu demonstrieren und den Algorithmus zur Berechnung der T_st-Teilsummen zu implementieren.