It is necessary to solve the problem with the help of Python: There is a set of financial instruments (even 10 pieces). There is the amount of the investment portfolio.

It is necessary to find ALL possible distribution of shares from the total amount of the investment portfolio attributable to each instrument (including 0%). The total amount should be = 100%. Step set (albeit 2%). Those. percent values ​​0,2,4,6 ..100%. Example: [14, 6, 10, 6, 10, 0, 16, 24, 2, 12].

Option vlob:

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))

Considers very long.

I tried tricks that reduce the set by the condition <= 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)

Already more real, but still long.

How to achieve faster work speed?

Example for step = 25.0 and the number of tools num_of_tickers = 4:

Possible percentage values:

 [0.0, 25.0, 50.0, 75.0, 100.0]

The output should be a table of distribution of the form:

 0, 0, 0, 100 0, 0, 25, 75 0, 25, 0, 75 25, 0, 0, 75 25, 0, 25, 50 ... 100, 0, 0, 0
  • not defined in your question: num_of_tickers , MAX_SHARE_SUM - MaxU
  • Yes, I am sorry, corrected. num_of_tickers number of instruments. MAX_SHARE_SUM = 100% - Rapohin Dmitriy
  • There is no input table in principle. From the input data - the number of instruments and the percentage step. Added an example to the question for step = 25.0 - Rapohin Dmitriy
  • well, nontrivial task - it’s impossible to solve it without thinking ... We have to think ... - MaxU
  • one
    @craneua You probably did not quite understand the question. The number of financial instruments is fixed at baseline. And 2 in your example is the percentage share of the initial capital attributable to this instrument - Rapohin Dmitriy

2 answers 2

The task is reduced to enumeration of compositions / expansions of a natural number (weak сompositions) for a 100 / step integer number:

 #!/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])

where weak_composition(k, n) is a readable implementation from the answer @ user3736966 to a similar question on 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,)

Example:

 >>> 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

Result for 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

Result for 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 ...

Related Questions:

  • Thank you, I will still understand the details. On 6 instruments, the speed of calculation is much faster than in my version. - Rapohin Dmitriy pm

to Rapohin Dmitriy I took your example: [14, 6, 10, 6, 10, 0, 16, 24, 2, 12], just to speed up it sorted it in descending order.

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

And if you output the results to a file and take into account all the remarks of the critics, and not assistants in solving the issue, then by modifying the code written in 5 minutes we get the result in 1 second:

2016-07-04 11: 27: 36.710029 24 16 14 12 10 10 6 6 2 0 Total options: 23436 2016-07-04 11: 27: 37.442615

  • This is some kind of tin. Why re-sort ls for each k0 - k9? This is definitely not optimization, it is anti-optimization. You could simply make k = sorted(ls, reverse=True) , then initialize the list of r cycle (rather than 10 separate variables). - insolor pm
  • @craneua, could you give the result of the work of your option for the conditions step == 25%, the number of tools == 4? Then we can compare it with what jfs has in response. - Rapohin Dmitriy 6:48 pm
  • Please give the percentages of these 4 tools - craneua
  • also 35 options - craneua
  • @craneua, to solve the problem, no more input data than the step and number of tools is required. The result of the work should be as in the jfs answer under the heading "Result for step == 25, number_of_tickets == 4". If you need any other input data, it means that you, nevertheless, misunderstood the task. - Rapohin Dmitriy