11
$\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?

$\endgroup$
  • 1
    $\begingroup$ Is 1+2+3 different from 3+2+1? $\endgroup$ – Aryabhata Jan 23 '11 at 22:07
  • $\begingroup$ No; partitions are unordered. $\endgroup$ – Will Vousden Jan 23 '11 at 22:09
  • 3
    $\begingroup$ Knuth's AoCP Volume 4, under the 'Generating all partitions' section, page 2, Algorithm H? $\endgroup$ – user4143 Jan 24 '11 at 5:02
16
$\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$
  • $\begingroup$ 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! $\endgroup$ – Will Vousden Jan 23 '11 at 23:24
  • $\begingroup$ @Will: Are you sure? I think that should work fine; that's what maxval is for. $\endgroup$ – Sophie Alpert Jan 24 '11 at 1:11
  • $\begingroup$ 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. $\endgroup$ – Peter Taylor Jan 24 '11 at 7:17
  • $\begingroup$ 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 :) $\endgroup$ – Will Vousden Jan 24 '11 at 15:35
  • 2
    $\begingroup$ @Will, I think it's to stop abuse of the system. Don't worry about it. $\endgroup$ – Peter Taylor Jan 24 '11 at 17:04
2
$\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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\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 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 :)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.