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; }; } #### my @set = @ARGV ? @ARGV : 1 .. 4; my $iter = set_partitions(@set); my $total; while ( my @part = $iter->() ) { $total++; print join(" ", map { "[@$_]" } @part), $/; } print "There are $total partitions of @set\n"; sub set_partitions { my @universe = @_; my @growth; return sub { if (!@growth) { @growth = (0) x @universe; return [ @universe ]; } return if $growth[-1] == $#growth; my $i = $#growth; $growth[$i--] = 0 while $growth[$i-1] == $growth[$i] - 1; $growth[$i]++; my @return; push @{ $return[$growth[$_]] }, $universe[$_] for 0 .. $#growth; return @return; }; }