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.

• John Coleman: You don't seem to be talking about partitions at all so much as linear combinations of nonnegative integers.
• PM 2Ring: I've added a general solution to my answer, in case you're interested.

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)

• Edgar Navasardyan: Well, PM 2Ring. What can I say. You and Python made my day. I am just beginning to feel the power of python
• PM 2Ring: @EdgarNavasardyan I'm glad you like it. It was literally a 5 minute hack. :) Actually, I just realised that it can be made slightly more efficient by moving the tests. :oops:
• John Coleman: Nice. I'd upvote your edit if I could (I already upvoted your original answer). I'm not surprised that an iterative approach is faster than a recursive approach. There is also probably a slick way to write a nonrecursive approach which makes heavy use of itertools.
• PM 2Ring: @JohnColeman: No worries (I've upvoted your answer, too). Hopefully the OP will find it interesting, or some future reader will get some use out of it. :)

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.

• PM 2Ring: That's rather compact! I've just written an iterative general solution. It's faster than your recursive code, but it's somewhat harder to read.

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

• John Coleman: The number of integer partitions of all integers in the range 800 to 1000 is unfeasibly large (the Wikipedia article on integer partitions gives 2.4 x 10^31 partitions of the number 1000 itself). If this is what OP wants, they are out of luck. They seem to want something much more limited, but need to clarify just what that is.
• PM 2Ring: @JohnColeman FWIW, there's some nice iterative partitioning code in Python by Jerome Kelleher on his site; I used it last year on a SE Mathematics answer.