#python #алгоритм
Необходимо с помощью 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
Ответы
Ответ 1
Задача сводится к перебору композиций/разложений натурального числа (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='\n') 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Ответ 2
to Rapohin Dmitriy Я и взял ваш пример: [14, 6, 10, 6, 10, 0, 16, 24, 2, 12], только для ускорения отсортировал его по убыванию. import sys import datetime def variant(i0, i1, i2, i3, i4, i5, i6, i7, i8, i9): ls = [i0, i1, i2, i3, i4, i5, i6, i7, i8, i9] k0 = sorted(ls, reverse=True)[0] k1 = sorted(ls, reverse=True)[1] k2 = sorted(ls, reverse=True)[2] k3 = sorted(ls, reverse=True)[3] k4 = sorted(ls, reverse=True)[4] k5 = sorted(ls, reverse=True)[5] k6 = sorted(ls, reverse=True)[6] k7 = sorted(ls, reverse=True)[7] k8 = sorted(ls, reverse=True)[8] k9 = sorted(ls, reverse=True)[9] pa = 100 if k0 == 0: r0 = 1 else: r0 = int(pa / k0) + 1 if k1 == 0: r1 = 1 else: r1 = int(pa / k1) + 1 if k2 == 0: r2 = 1 else: r2 = int(pa / k2) + 1 if k3 == 0: r3 = 1 else: r3 = int(pa / k3) + 1 if k4 == 0: r4 = 1 else: r4 = int(pa / k4) + 1 if k5 == 0: r5 = 1 else: r5 = int(pa / k5) + 1 if k6 == 0: r6 = 1 else: r6 = int(pa / k6) + 1 if k7 == 0: r7 = 1 else: r7 = int(pa / k7) + 1 if k8 == 0: r8 = 1 else: r8 = int(pa / k8) + 1 if k9 == 0: r9 = 1 else: r9 = int(pa / k9) + 1 c = 0 s = 0 print(k0,' ',k1,' ',k2,' ',k3,' ',k4,' ',k5,' ',k6,' ',k7,' ',k8,' ',k9) for c0 in range(r0): s0 = c0 * k0 for c1 in range(r1): s1 = c1 * k1 if s1 + s0 > pa: break for c2 in range(r2): s2 = c2 * k2 if s2 + s1 + s0 > pa: break for c3 in range(r3): s3 = c3 * k3 if s3 + s2 + s1 + s0 > pa: break for c4 in range(r4): s4 = c4 * k4 if s4 + s3 + s2 + s1 + s0 > pa: break for c5 in range(r5): s5 = c5 * k5 if s5 + s4 + s3 + s2 + s1 + s0 > pa: break for c6 in range(r6): s6 = c6 * k6 if s6 + s5 + s4 + s3 + s2 + s1 + \ s0 > pa: break for c7 in range(r7): s7 = c7 * k7 if s7 + s6 + s5 + s4 + s3 + s2 + \ s1 + s0 > pa: break for c8 in range(r8): s8 = c8 * k8 if s8 + s7 + s6 + s5 + s4 + \ s3 + s2 + s1 + s0 > pa: break for c9 in range(r9): s9 = c9 * k9 s = s9 + s8 + s7 + s6 + s5 + \ s4 + s3 + s2 + s1 + s0 if s < pa: pass elif s == pa: print(c0*k0, c1*k1, c2*k2, c3*k3, c4*k4, c5*k5, c6*k6, c7*k7, c8*k8, c9*k9) c += 1 else: break print('Всего вариантов: ', c) return print(datetime.datetime.now()) variant(14, 6, 10, 6, 10, 0, 16, 24, 2, 12) print(datetime.datetime.now()) А если выводить результаты в файл и учесть все замечания критиканов, а не помощников в решении вопроса, то модифицировав код написанный за 5 минут получим результат за 1 секунду: 2016-07-04 11:27:36.710029 24 16 14 12 10 10 6 6 2 0 Всего вариантов: 23436 2016-07-04 11:27:37.442615
Комментариев нет:
Отправить комментарий