Python Integer Partitioning with given k partitions
algorithm, integer-partition, python
Solution
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.
Problem
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`