Edgar Navasardyan Edgar Navasardyan - 5 months ago 13
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.

Answer

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