# Algorithm for generating integer partitions up to a certain maximum length

I'm looking for a fast algorithm for generating all the partitions of an integer up to a certain maximum length; ideally, I don't want to have to generate all of them and then discard the ones that are too long, as this will take around 5 times longer in my case.

Specifically, given $$L = N(N+1)$$, I need to generate all the partitions of $$L$$ that have at most $$N$$ parts. I can't seem to find any algorithms that'll do this directly; all I've found that seems relevant is this paper, which I unfortunately can't seem to access via my institution's subscription. It apparently1 documents an algorithm that generates the partitions of each individual length, which could presumably be easily adapted to my needs.

Does anyone know of any such algorithms?

1Zoghbi, Antoine; Stojmenović, Ivan, Fast algorithms for generating integer partitions, Int. J. Comput. Math. 70, No. 2, 319-332 (1998). ZBL0918.68040, MR1712501. Wayback Machine

• Is 1+2+3 different from 3+2+1? Commented Jan 23, 2011 at 22:07
• No; partitions are unordered. Commented Jan 23, 2011 at 22:09
• Knuth's AoCP Volume 4, under the 'Generating all partitions' section, page 2, Algorithm H? Commented Jan 24, 2011 at 5:02

You can do it recursively. Let $f(n, maxcount, maxval)$ return the list of partitions of $n$ containing no more than $maxcount$ parts and in which each part is no more than $maxval$.

If $n = 0$ you return a single list containing the empty partition.

If $n > maxcount * maxval$ you return the empty list.

If $n = maxcount * maxval$ you return a single list consisting of the obvious solution.

Otherwise you make a series of recursive calls to $f(n - x, maxcount - 1, x)$.

• I'm actually already using this approach, but it generates compositions rather than partitions (i.e. they're ordered), which isn't what I want in this case. Obviously for large $n$ this makes the number of results somewhat unmanageable! Thanks, though! Commented Jan 23, 2011 at 23:24
• @Will: Are you sure? I think that should work fine; that's what maxval is for. Commented Jan 24, 2011 at 1:11
• This algorithm can generate each partition with their elements ordered from greatest to least - it's just a matter of prepending x to the partitions obtained from the recursive call. Or it can generate them ordered from least to greatest - postpend. Commented Jan 24, 2011 at 7:17
• You're absolutely right, my bad! My existing implementation was lacking the maximum value logic present in yours. This indeed works as required now, thanks :) Commented Jan 24, 2011 at 15:35
• @Will, I think it's to stop abuse of the system. Don't worry about it. Commented Jan 24, 2011 at 17:04

If you are only interested in using an actual implementation, you could go for the integer_partitions(n[, length]) in Maxima. More details can be found here.

This can be done with a very simple modification to the ruleAsc algorithm at http://jeromekelleher.net/category/combinatorics.html

 def ruleAscLen(n, l):
a = [0 for i in range(n + 1)]
k = 1
a[0] = 0
a[1] = n
while k != 0:
x = a[k - 1] + 1
y = a[k] - 1
k -= 1
while x <= y and k < l - 1:
a[k] = x
y -= x
k += 1
a[k] = x + y
yield a[:k + 1]


This generates all partitions of n into at most l parts (changing your notation around a bit). The algorithm is constant amortised time, so the time spent per partition is constant, on average.

This article about Gray codes includes partitions. The idea behind a Gray code is to enumerate a cyclic sequence of some combinatorial collection of objects so that the "distance" between consecutive items in the list are "close." http://linkinghub.elsevier.com/retrieve/pii/0196677489900072 Savage also has other survey articles about Gray codes that include partitions. http://reference.kfupm.edu.sa/content/s/u/a_survey_of_combinatorial_gray_codes__213043.pdf

I was looking for an algorithm that generates all partitions of $$L$$ into $$N$$ parts in the multiplicity representation, Knuth calls it the "part-count form". I only found algorithm Z from A. Zoghbi's 1993 thesis http://dx.doi.org/10.20381/ruor-11312 to output partitions in this form but it generates all partitions of $$L$$. I coded it up as partition(L) in C++ and added a slight modification to only generate partitions into $$N$$ parts, partition(L, N). I put the code with both functions on github as a gist. Both have the same update to go from one partition to the next and just need a different initialization.

Zogbi claims that the multiplicity form is faster, his algorithm Z is just a transform of algorithm H mentioned in Knuth's TAOCP 4 to partition $$L$$ into $$N$$ parts in standard representation but Z was at least 2x faster than H in their tests, albeit on 1993 hardware :)

• Knuth usually abbreviates "The Art of Computer Programming" to TAOCP. Commented Jul 22, 2021 at 10:12