Edgar Navasardyan - 1 year ago 115
Python Question

# Algorithm for generating partitions of number

My goal is to get all partitions of a given number S decomposed by predefined values so that the sum is less than S and greater than 0.8S.
For example, S = 1000, and we want to decompose 1000 into a sum of type 17x + 20y + 150z, so that 17x + 20y + 150z is less than 1000 and greater than 800.

I've come across a solution of a similar problem, but I am having trouble understanding how can I store the values into an array.

You don't need a full partition algorithm here. You can find the numbers you want with simple looping. If you have a fixed number of coefficients, as given in the question, then you can just use a few `for` loops. If the number of coefficients can vary, then you'll need a more sophisticated solution.

Here I find numbers that fit your pattern in the range 990 to 1000 (inclusive), to make the output manageable, since there are 1284 combinations of x, y, and z for the range from 800 to 1000.

I assume you want to do something with these solutions, so I save them in a list for further processing.

``````from itertools import count

mx, my, mz = 17, 20, 150
lo = 990
hi = 1000

solns = []
for z in count(1):
sz = z * mz
if sz > hi:
break
for y in count(1):
sy = sz + y * my
if sy > hi:
break
d = lo - sy
x = max(1, -(-d // mx))
for x in count(x):
s = sy + x * mx
if s > hi:
break
t = (z, y, x, s)
solns.append(t)

print(len(solns))
for t in solns:
print(t)
``````

output

``````86
(1, 3, 46, 992)
(1, 4, 45, 995)
(1, 5, 44, 998)
(1, 8, 40, 990)
(1, 9, 39, 993)
(1, 10, 38, 996)
(1, 11, 37, 999)
(1, 14, 33, 991)
(1, 15, 32, 994)
(1, 16, 31, 997)
(1, 17, 30, 1000)
(1, 20, 26, 992)
(1, 21, 25, 995)
(1, 22, 24, 998)
(1, 25, 20, 990)
(1, 26, 19, 993)
(1, 27, 18, 996)
(1, 28, 17, 999)
(1, 31, 13, 991)
(1, 32, 12, 994)
(1, 33, 11, 997)
(1, 34, 10, 1000)
(1, 37, 6, 992)
(1, 38, 5, 995)
(1, 39, 4, 998)
(2, 1, 40, 1000)
(2, 4, 36, 992)
(2, 5, 35, 995)
(2, 6, 34, 998)
(2, 9, 30, 990)
(2, 10, 29, 993)
(2, 11, 28, 996)
(2, 12, 27, 999)
(2, 15, 23, 991)
(2, 16, 22, 994)
(2, 17, 21, 997)
(2, 18, 20, 1000)
(2, 21, 16, 992)
(2, 22, 15, 995)
(2, 23, 14, 998)
(2, 26, 10, 990)
(2, 27, 9, 993)
(2, 28, 8, 996)
(2, 29, 7, 999)
(2, 32, 3, 991)
(2, 33, 2, 994)
(2, 34, 1, 997)
(3, 1, 31, 997)
(3, 2, 30, 1000)
(3, 5, 26, 992)
(3, 6, 25, 995)
(3, 7, 24, 998)
(3, 10, 20, 990)
(3, 11, 19, 993)
(3, 12, 18, 996)
(3, 13, 17, 999)
(3, 16, 13, 991)
(3, 17, 12, 994)
(3, 18, 11, 997)
(3, 19, 10, 1000)
(3, 22, 6, 992)
(3, 23, 5, 995)
(3, 24, 4, 998)
(4, 1, 22, 994)
(4, 2, 21, 997)
(4, 3, 20, 1000)
(4, 6, 16, 992)
(4, 7, 15, 995)
(4, 8, 14, 998)
(4, 11, 10, 990)
(4, 12, 9, 993)
(4, 13, 8, 996)
(4, 14, 7, 999)
(4, 17, 3, 991)
(4, 18, 2, 994)
(4, 19, 1, 997)
(5, 1, 13, 991)
(5, 2, 12, 994)
(5, 3, 11, 997)
(5, 4, 10, 1000)
(5, 7, 6, 992)
(5, 8, 5, 995)
(5, 9, 4, 998)
(6, 2, 3, 991)
(6, 3, 2, 994)
(6, 4, 1, 997)
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download