comment on

Update: bah, that crafty tye previously posted essentially the same iterator...

I wrote up this iterator a while ago for some now-long-forgotten purpose. I just found it laying around, so I thought I should post it..

An integer partition of n is a set of positive integers which adds up to n. For instance, the integer partitions of 5 are:

5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1

Note that we do not care about the order of terms in the addition.

This iterator generates all the integer partitions of a given number. It's an implementation of the very simple algorithm from this paper.

It has the nice feature that it is memoryless -- that is, it is not a closure which keeps internal state. To get the next partition in the sequence, just pass in the previous one. In this sense, it is similar to tye's memoryless iterator for permutations.

This iterator outputs the partitions in reverse lexicographic order. Since the first partition of N in this ordering is just the singleton list containing N itself, all you have to do to start it up is call it with the single argument N. There is no real error checking built-in -- you have to call it with a list of positive integers.

sub nextpart {
    ## collect all the trailing 1s
    my $x = 0;
    $x += pop while @_ and $_[-1] == 1;
    return if ! @_;

    ## collect 1 from the rightmost remaining guy
    $_[-1]--; $x++;

    ## re-distribute the collected amount in increments of $_[-1]
    while ($x > $_[-1]) {
       push @_, $_[-1];
       $x -= $_[-1];
    }
    push @_, $x;

    @_;
}

## example usage:

my @part = (5);
do {
    print "@part\n";
} while (@part = nextpart @part);

__OUTPUT__
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1
[download]

In reply to Memoryless iterator for integer partitions by blokhead

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or How to display code and escape characters are good places to start.


"be consistent"
	PerlMonks