Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"

Memoryless iterator for integer partitions

by blokhead (Monsignor)
on Jun 18, 2007 at 19:44 UTC ( #621859=snippet: print w/replies, xml ) Need Help??
Description: 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.

See also: Generator of integer partitionts of n, RFC: Integer::Partition::Unrestricted, How to generate restricted partitions of an integer, puzzle: how many ways to make $100, integer partition golf

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);

4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1
Replies are listed 'Best First'.
Re: Memoryless iterator for integer partitions
by grinder (Bishop) on Jun 18, 2007 at 20:59 UTC

    Interesting. I needed to generate some integer partitions myself for something I was working on the other day and I was surprised to discover that there wasn't anything already available on CPAN.

    I searched around, and ran across the same paper. I imemplented both algorithms proposed by Zoghbi and Stojmenovic in that paper, to permit forward and reverse lexicographic orderings and released it as a module.

    My only comment is that while your code is very consice, I think you have removed the constant average delay property that the original algorithm features. The algorithm only requires two scalars to maintain state, so it's not as if its a memory pig.

    • another intruder with the mooring in the heart of the Perl

Re: Memoryless iterator for integer partitions
by Limbic~Region (Chancellor) on Jun 19, 2007 at 13:24 UTC
Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: snippet [id://621859]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (6)
As of 2017-02-22 16:26 GMT
Find Nodes?
    Voting Booth?
    Before electricity was invented, what was the Electric Eel called?

    Results (331 votes). Check out past polls.