Algorithm for generating integer partitions up to a certain maximum length

Question

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 apparently ¹ 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?

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

• Aryabhata: Is 1+2+3 different from 3+2+1?
• Will Vousden: No; partitions are unordered.
• user4143: Knuth's AoCP Volume 4, under the 'Generating all partitions' section, page 2, Algorithm H?

Answer 1

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)$.

• Will Vousden: 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!
• Sophie Alpert: @Will: Are you sure? I think that should work fine; that's what maxval is for.
• Peter Taylor: 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.
• Will Vousden: 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 :)
• Peter Taylor: @Will, I think it's to stop abuse of the system. Don't worry about it.

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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

• Marc van Leeuwen: Knuth usually abbreviates "The Art of Computer Programming" to TAOCP.