12
$\begingroup$

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?

  • 3
    Knuth's [AoCP Volume 4](http://cs.utsa.edu/~wagner/knuth/), under the 'Generating all partitions' section, page 2, [Algorithm H](http://cs.utsa.edu/~wagner/knuth/fasc3b.pdf)?2011-01-24

5 Answers 5

17

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

  • 2
    @Will, I think it's to stop abuse of the system. Don't worry about it.2011-01-24
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.

2

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.

0

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

0

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