snippet
blokhead
<b>Update:</b> bah, that crafty [tye] previously [id://78526|posted] essentially the same iterator...
<p>
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..
<p>
An integer partition of n is a set of positive integers which adds up to n. For instance, the
integer partitions of 5 are:
<blockquote>5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1</blockquote>
Note that we do not care about the order of terms in the addition.
<p>
This iterator generates all the integer partitions of a given number. It's an implementation of the very simple algorithm from [http://www.site.uottawa.ca/~ivan/F49-int-part.pdf|this paper].
<p>
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 [id://29374|permutations].
<p>
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.
<p>
See also: [id://386531], [id://533164], [id://406984], [id://546438], [id://579156]
<CODE>
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
</CODE>