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; }; } ```