Необходимо с помощью 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
