Python Integer Partitioning with given k partitions

Question

I'm trying to find or develop Integer Partitioning code for Python.

FYI, Integer Partitioning is representing a given integer n as a sum of integers smaller than n. For example, an integer 5 can be expressed as 4 +たす 1 =わ 3 +たす 2 =わ 3 +たす 1 +たす 1 =わ 2 +たす 2 +たす 1 =わ 2 +たす 1 +たす 1 +たす 1 =わ 1 +たす 1 +たす 1 +たす 1 +たす 1

I've found a number of solutions for this. http://homepages.ed.ac.uk/jkellehe/partitions.php and http://code.activestate.com/recipes/218332-generator-for-integer-partitions/

However, what I really want is to restrict the number of partitions.

Say, # of partition k = 2, a program only need to show 5 =わ 4 +たす 1 =わ 3 +たす 2,

if k = 3, 5 =わ 3 +たす 1 +たす 1 =わ 2 +たす 2 +たす 1

• AI Generated Response: You only want a certain number of partitions?
• user2211319: Yes, that's right. Say partitionfunc(n, k) would give list of partitions of integer n whose length is k
• user2357112: Wait, do you want fixed-length partitions, or do you want to only generate a certain number of partitions?
• user2211319: length of partitions k will be given by user's input, as well as n
• Graham: @DavidEisenstat This is a distinct problem from the linked question, which is about doubly restricted integer partitioning (though the title of the linked question is misleading.)

Answer 1

I've written a generator solution

def partitionfunc(n,k,l=1):
 '''n is the integer to partition, k is the length of partitions, l is the min partition element size'''
 if k < 1:
 raise StopIteration
 if k == 1:
 if n >= l:
 yield (n,)
 raise StopIteration
 for i in range(l,n+1):
 for result in partitionfunc(n-i,k-1,i):
 yield (i,)+result

This generates all the partitions of n with length k with each one being in order of least to greatest.

Just a quick note: Via cProfile, it appears that using the generator method is much faster than using falsetru's direct method, using the test function lambda x,y: list(partitionfunc(x,y)). On a test run of n=50,k-5, my code ran in .019 seconds vs the 2.612 seconds of the direct method.

• falsetru: You can use return instead of raise StopIteration.
• falsetru: I updated my list concatenation version. Still slower than your code, but improved. :)
• saulspatz: You can change for i in range(l, n+1) to for i in range(l, n//k+1) since you can't have k parts bigger than n//k.
• Lars: I found a non-recursive solution: stackoverflow.com/questions/60639740/…
• AviKKi: raise StopIteration is deprecated now as shown here ; raise StopIteration should be replace with return statement.

Answer 2

def part(n, k):
 def _part(n, k, pre):
 if n <= 0:
 return []
 if k == 1:
 if n <= pre:
 return [[n]]
 return []
 ret = []
 for i in range(min(pre, n), 0, -1):
 ret += [[i] + sub for sub in _part(n-i, k-1, i)]
 return ret
 return _part(n, k, n)

Example:

>>> part(5, 1)
[[5]]
>>> part(5, 2)
[[4, 1], [3, 2]]
>>> part(5, 3)
[[3, 1, 1], [2, 2, 1]]
>>> part(5, 4)
[[2, 1, 1, 1]]
>>> part(5, 5)
[[1, 1, 1, 1, 1]]
>>> part(6, 3)
[[4, 1, 1], [3, 2, 1], [2, 2, 2]]

UPDATE

Using memoization:

def part(n, k):
 def memoize(f):
 cache = [[[None] * n for j in xrange(k)] for i in xrange(n)]
 def wrapper(n, k, pre):
 if cache[n-1][k-1][pre-1] is None:
 cache[n-1][k-1][pre-1] = f(n, k, pre)
 return cache[n-1][k-1][pre-1]
 return wrapper
 @memoize
 def _part(n, k, pre):
 if n <= 0:
 return []
 if k == 1:
 if n <= pre:
 return [(n,)]
 return []
 ret = []
 for i in xrange(min(pre, n), 0, -1):
 ret += [(i,) + sub for sub in _part(n-i, k-1, i)]
 return ret
 return _part(n, k, n)

Answer 3

First I want to thanks everyone for their contribution. I arrived here needing an algorithm for generating integer partitions with the following details :

Generate partitions of a number into EXACTLY k parts but also having MINIMUM and MAXIMUM constraints.

Therefore, I modified the code of "Snakes and Coffee" to accommodate these new requirements:

def partition_min_max(n, k, l, m):
 ''' n is the integer to partition, k is the length of partitions, 
 l is the min partition element size, m is the max partition element size '''
 if k < 1:
 raise StopIteration
 if k == 1:
 if n <= m and n>=l :
 yield (n,)
 raise StopIteration
 for i in range(l,m+1):
 for result in partition_min_max(n-i, k-1, i, m):
 yield result+(i,)
>>> x = list(partition_min_max(20 ,3, 3, 10 ))
>>> print(x)
>>> [(10, 7, 3), (9, 8, 3), (10, 6, 4), (9, 7, 4), (8, 8, 4), (10, 5, 5), (9, 6, 5), (8, 7, 5), (8, 6, 6), (7, 7, 6)]

Answer 4

Building upon previous answer with maximum and minimum constraints, we can optimize it be a little better . For eg with k = 16 , n = 2048 and m = 128 , there is only one such partition which satisfy the constraints(128+128+...+128). But the code searches unnecessary branches for an answer which can be pruned.

def partition_min_max(n,k,l,m):
#n is the integer to partition, k is the length of partitions, 
#l is the min partition element size, m is the max partition element size
 if k < 1:
 return
 if k == 1:
 if n <= m and n>=l :
 yield (n,)
 return
 if (k*128) < n: #If the current sum is too small to reach n
 return
 if k*1 > n:#If current sum is too big to reach n
 return
 for i in range(l,m+1):
 for result in partition_min_max(n-i,k-1,i,m): 
 yield result+(i,)