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>