Algorithm for generating partitions of number

Question

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 1

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)

I suppose I should explain this slightly mysterious line of code:

x = max(1, -(-d // mx))

// is the floor division operator, a // b returns the greatest integer less than or equal to a/b.

Thus -d // mx is the greatest integer <= -d/mx, and -(-d // mx) is therefore the lowest integer >= d/mx. However, this can sometimes yield non-positive values (when sy >= lo); when that occurs the max function ensures that 1 is the lowest value assigned to x.

---

After seeing John Coleman's more general solution I was inspired to write one too. Mine isn't as compact or as easy to read as John's but it uses iteration instead of recursion, and it uses less memory. It's also about twice as fast, although it's roughly 20% slower than my original version that can only handle 3 coefficients.

Instead of returning a list, this code is a generator. So you can either use the results as it yields them, or you can gather the results into a list or some other collection, eg a dict of lists, with each list containing tuples that correspond to a given sum, with the sum as the key for that list.

def linear_sum(lo, hi, coeff):
    ''' Find all positive integer solutions of the linear equation with 
        coefficients `coeff` with sum `s`: lo <= s <= hi 
    '''
    num = len(coeff)
    vector = [1] * num
    mx = coeff[-1]
    s = sum(coeff[:-1])
    while True:
        olds = s
        xlo = max(1, -((s - lo) // mx))
        xhi = 1 + (hi - s) // mx
        s += mx * xlo
        for vector[-1] in range(xlo, xhi):
            yield s, tuple(vector)
            s += mx

        # Increment next vector component
        k = num - 2
        vector[k] += 1
        s = olds + coeff[k]

        # If the component is too high 
        while s > hi:
            if not k:
                return

            # reset this component,
            s -= coeff[k] * (vector[k] - 1)
            vector[k] = 1

            # and increment the next component.
            k -= 1
            vector[k] += 1
            s += coeff[k]

# Tests

coeff = 150, 20, 17

# Create a list    
solns = [v for v in linear_sum(800, 1000, coeff)]
print(len(solns))

# Generate solutions one by one and verify that they give the correct sum
for s, vector in linear_sum(990, 1000, coeff):
    assert s == sum(u*v for u, v in zip(coeff, vector))
    print(s, vector)

output

1284
992 (1, 3, 46)
995 (1, 4, 45)
998 (1, 5, 44)
990 (1, 8, 40)
993 (1, 9, 39)
996 (1, 10, 38)
999 (1, 11, 37)
991 (1, 14, 33)
994 (1, 15, 32)
997 (1, 16, 31)
1000 (1, 17, 30)
992 (1, 20, 26)
995 (1, 21, 25)
998 (1, 22, 24)
990 (1, 25, 20)
993 (1, 26, 19)
996 (1, 27, 18)
999 (1, 28, 17)
991 (1, 31, 13)
994 (1, 32, 12)
997 (1, 33, 11)
1000 (1, 34, 10)
992 (1, 37, 6)
995 (1, 38, 5)
998 (1, 39, 4)
1000 (2, 1, 40)
992 (2, 4, 36)
995 (2, 5, 35)
998 (2, 6, 34)
990 (2, 9, 30)
993 (2, 10, 29)
996 (2, 11, 28)
999 (2, 12, 27)
991 (2, 15, 23)
994 (2, 16, 22)
997 (2, 17, 21)
1000 (2, 18, 20)
992 (2, 21, 16)
995 (2, 22, 15)
998 (2, 23, 14)
990 (2, 26, 10)
993 (2, 27, 9)
996 (2, 28, 8)
999 (2, 29, 7)
991 (2, 32, 3)
994 (2, 33, 2)
997 (2, 34, 1)
997 (3, 1, 31)
1000 (3, 2, 30)
992 (3, 5, 26)
995 (3, 6, 25)
998 (3, 7, 24)
990 (3, 10, 20)
993 (3, 11, 19)
996 (3, 12, 18)
999 (3, 13, 17)
991 (3, 16, 13)
994 (3, 17, 12)
997 (3, 18, 11)
1000 (3, 19, 10)
992 (3, 22, 6)
995 (3, 23, 5)
998 (3, 24, 4)
994 (4, 1, 22)
997 (4, 2, 21)
1000 (4, 3, 20)
992 (4, 6, 16)
995 (4, 7, 15)
998 (4, 8, 14)
990 (4, 11, 10)
993 (4, 12, 9)
996 (4, 13, 8)
999 (4, 14, 7)
991 (4, 17, 3)
994 (4, 18, 2)
997 (4, 19, 1)
991 (5, 1, 13)
994 (5, 2, 12)
997 (5, 3, 11)
1000 (5, 4, 10)
992 (5, 7, 6)
995 (5, 8, 5)
998 (5, 9, 4)
991 (6, 2, 3)
994 (6, 3, 2)
997 (6, 4, 1)

Answer 2

Here is a recursive approach that, given a lower bound, a, an upper bound, b, and a list of coefficients, nums, returns a list of vectors of nonnegative integers which when multiplied by the respective coefficients and then summed, returns an sum between a and b inclusive. The function allows 0 as a value. But note that e.g., there is an easy one-to-one correspondence between integer solutions (x,y,z) with x,y,z >= 1 and

990 <= 17x + 20y + 150z <= 1000

and the solutions (x,y,z) with x,y,z >= 0 and

990 - 187 <= 17x + 20y + 150z <= 1000 - 187

Here is the code:

import math

def allSolutions(a,b,nums):
    if len(nums) == 0:
        return []

    c = nums[0]
    m = max(0,math.ceil(a/c))
    M = math.floor(b/c)

    if len(nums) == 1:
        return [(x,) for x in range(m,M+1)]

    solutions = []
    for x in range(M+1):
        solutions.extend((x,)+s for s in allSolutions(a-c*x,b-c*x,nums[1:]))
    return solutions

For example, allSolutions(990-187,1000-187,[17,20,150]) yields essentially the same 86 solutions as @PM2Ring found in their excellent answers. allSolutions(800-187,1000-187,[17,20,150]) finds 1284 solutions as well.

Answer 3

From what I understand, you don't want to generate actual partitions of S, because then this wouldn't make sense:

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

If it's less than 1000, it won't be a partition of 1000.

So I assume you want to generate the partitions of all numbers from 0.8S to S.

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.

Simply do list(partitions(n)). For your problem:

[list(partitions(i)) for i in range(int(0.8*S), S)]

Where partitions is the function you linked to, posted by David Eppstein, which I will copy below:

def partitions(n):
    # base case of recursion: zero is the sum of the empty list
    if n == 0:
        yield []
        return

    # modify partitions of n-1 to form partitions of n
    for p in partitions(n-1):
        yield [1] + p
        if p and (len(p) < 2 or p[1] > p[0]):
            yield [p[0] + 1] + p[1:]