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
$\endgroup$ 35 Answers
$\begingroup$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)$.
$\endgroup$ 6 $\begingroup$This can be done with a very simple modification to the ruleAsc algorithm at
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.
$\endgroup$ $\begingroup$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 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." Savage also has other survey articles about Gray codes that include partitions.
$\endgroup$ $\begingroup$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 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 :)
$\endgroup$ 1
