Продвинутая комбинаторика в Python: биномные (n,2) подмножества биномных (n,3) комбинаций без повторения ⇐ Python

[Anonymous]

У меня есть список d_n из n целых чисел и результаты Z_klm функции fun(dk, dl, dm) для всех биномов (n, 3) комбинаций без повторений (k, l, m) из d_n индексов.
Теперь для всех биномов (n, 2) комбинаций без повторений (s, t) индексов d_n, мне нужно взять частичные суммы T_st Z_klm, где (s, t) — подмножество (k, l, m).
Вот пример с маленьким n.

Код: Выделить всё

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

Код: Выделить всё

(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]]})

Например, T_{2,4} — это сумма Z_{0,2,4}, Z_{1,2,4} и Z_{2,3,4}.
Моя грубая реализация работает только потому, что здесь очень мало наблюдений. Но в случае реальных размеров выборки (обычно может достигать n = 1000) на перебор всего бинома(n,2) и бинома(n,3) потребуется целая жизнь.
Есть предложения по ускорению с помощью эффективного алгоритма или более продвинутых инструментов итерации?
P.S.: Мне не нужно хранить все (k, l, m) и (s, т) индексы; Я сделал это здесь только для того, чтобы продемонстрировать, как это работает, и реализовать алгоритм расчета частичных сумм T_st.

Подробнее здесь: https://stackoverflow.com/questions/798 ... mbinations