Как эффективно перебрать процентные распределения?

Необходимо с помощью Python решить задачу: Есть набор финансовых инструментов (пусть 10 штук). Есть сумма инвестиционного портфеля.
Необходимо найти ВСЕ возможные варианты распределения долей от общей суммы инвестиционного портфеля, приходящихся на каждый инструмент(включая 0%). Общая сумма должна быть = 100%. Шаг задан (пусть 2%). Т.е. значения процентов 0,2,4,6..100%. Пример: [14, 6, 10, 6, 10, 0, 16, 24, 2, 12].
Вариант влоб:
step = 2.0 num_of_tickers = 10 steps = math.floor(100.0 / step) + 1 share_lst = [idx * step for idx in range(0, steps)] comb_all = itertools.product(share_lst, repeat=num_of_tickers) comb_res = list(filter(lambda x: sum(x) == 100.0, comb_all))
Считает ОЧЕНЬ долго.
Пробовал ухищрения, сокращающие набор по условию <=100%:
comb_all = itertools.product(share_lst, repeat=5) comb_all_lst = list(filter(lambda x: sum(x) <= 100.0, comb_all)) for lst in comb_all_lst: for lst_1 in comb_all_lst: if (sum(lst) + sum(lst_1)) == 100.0: comb_res.append(lst + lst_1)
Уже реальнее, но все равно долго.
Как добиться более быстрой скорости работы?
Пример для step = 25.0 и числа инструментов num_of_tickers = 4:
Возможные значения процентной доли:
[0.0, 25.0, 50.0, 75.0, 100.0]
На выходе должна быть таблица распределений вида:
0, 0, 0, 100 0, 0, 25, 75 0, 25, 0, 75 25, 0, 0, 75 25, 0, 25, 50 ... 100, 0, 0, 0

Ответ

Задача сводится к перебору композиций/разложений натурального числа (weak сompositions) для 100 / step целого числа:
#!/usr/bin/env python3 import math
step = 2 n = 100 // step k = 10 # количество инструментов
def binom(n, k): f = math.factorial return f(n) // (f(k) * f(n - k))
print("Количество распределений:", binom(n+k-1, n)) for comp in weak_compositions(k, n): assert len(comp) == k and sum(n*step for n in comp) == 100 print(*[n*step for n in comp])
где weak_composition(k, n) это читаемая реализация из ответа @user3736966 на схожий вопрос на Stack Overflow
def weak_compositions(boxes, balls, parent=tuple()): if boxes > 1: for i in range(balls + 1): yield from weak_compositions(boxes - 1, i, parent + (balls - i,)) else: yield parent + (balls,)
Пример:
>>> print(*[' + '.join(map(str, c)) for c in weak_compositions(3, 5)], sep='
') 5 + 0 + 0 4 + 1 + 0 4 + 0 + 1 3 + 2 + 0 3 + 1 + 1 3 + 0 + 2 2 + 3 + 0 2 + 2 + 1 2 + 1 + 2 2 + 0 + 3 1 + 4 + 0 1 + 3 + 1 1 + 2 + 2 1 + 1 + 3 1 + 0 + 4 0 + 5 + 0 0 + 4 + 1 0 + 3 + 2 0 + 2 + 3 0 + 1 + 4 0 + 0 + 5
Результат для step == 25, number_of_tickets == 4
Количество распределений: 35 100 0 0 0 75 25 0 0 75 0 25 0 75 0 0 25 50 50 0 0 50 25 25 0 50 25 0 25 50 0 50 0 50 0 25 25 50 0 0 50 25 75 0 0 25 50 25 0 25 50 0 25 25 25 50 0 25 25 25 25 25 25 0 50 25 0 75 0 25 0 50 25 25 0 25 50 25 0 0 75 0 100 0 0 0 75 25 0 0 75 0 25 0 50 50 0 0 50 25 25 0 50 0 50 0 25 75 0 0 25 50 25 0 25 25 50 0 25 0 75 0 0 100 0 0 0 75 25 0 0 50 50 0 0 25 75 0 0 0 100
Результат для step == 2, number_of_tickets == 10
Количество распределений: 12565671261 100 0 0 0 0 0 0 0 0 0 98 2 0 0 0 0 0 0 0 0 98 0 2 0 0 0 0 0 0 0 ... 72 2 0 4 16 0 2 0 2 2 72 2 0 4 16 0 2 0 0 4 72 2 0 4 16 0 0 6 0 0 ...
Связанные вопросы:
Next Composition of n into k parts - does anyone have a working algorithm? Efficient lazy weak compositions