Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
Is 1+2+3 different from 3+2+1? –  Aryabhata Jan 23 '11 at 22:07
    
No; partitions are unordered. –  Will Vousden Jan 23 '11 at 22:09
1  
Knuth's AoCP Volume 4, under the 'Generating all partitions' section, page 2, Algorithm H? –  user4143 Jan 24 '11 at 5:02

4 Answers 4

up vote 6 down vote accepted

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

share|improve this answer
    
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! –  Will Vousden Jan 23 '11 at 23:24
    
@Will: Are you sure? I think that should work fine; that's what maxval is for. –  Ben Alpert Jan 24 '11 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. –  Peter Taylor Jan 24 '11 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 :) –  Will Vousden Jan 24 '11 at 15:35
1  
@Will, I think it's to stop abuse of the system. Don't worry about it. –  Peter Taylor Jan 24 '11 at 17:04

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

share|improve this answer

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.

share|improve this answer

This can be done with a very simple modification to the ruleAsc algorithm at http://homepages.ed.ac.uk/jkellehe/partitions.php

 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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