my $n = shift || 10;
my $iter = int_partitions($n);
my $total;
while ( my @part = $iter->() ) {
$total++;
print "@part\n";
}
print "There are $total partitions of $n\n";
sub int_partitions {
my $n = shift;
my @tally;
return sub {
if (!@tally) {
@tally = ( (0) x $n, 1 );
return ($n);
}
## last partition is $n 1's
return if $tally[1] == $n;
## take one away from smallest >1 part
my ($least) = grep { $tally[$_] } 2 .. $n;
$tally[$least]--;
$tally[$least-1]++;
$tally[1]++;
## collect multiple 1's into groups smaller than $least
while ( $least > 2 and $tally[1] > 1 ) {
my $move = ( sort { $a <=> $b } $least-1, $tally[1] )[0];
$tally[1] -= $move;
$tally[$move]++;
}
return map { ($_) x $tally[$_] } reverse 1 .. $n;
};
}