http://qs321.pair.com?node_id=806018

This is a multinomial coefficients problem. The assumptions are:

• no empty containers
• order of items in containers do not matter in the results
• order of containers do matter in the results

mult_coeff(3, qw(a b c d e)); yields 150 results, which corresponds to the math:
5! 5! ------------ * 3 + ------------ * 3 = 150 1! * 2! * 2! 1! * 1! * 3!

for combinations of 1-2-2, 2-1-2, 2-2-1, 1-1-3, 1-3-1, 3-1-1.

nck_with_leftover() should be memoized for performance.

A solution:
sub mult_coeff { my \$c = shift(); return [] if \$c <= 0; return [ [ @_ ] ] if \$c == 1; my @sets; for my \$k (1 .. @_ - \$c + 1) { for my \$nck_ref (nck_with_leftover(\$k, @_)) { push @sets, map { unshift(@{ \$_ }, [ @{ \$nck_ref-> } ]); # clone r +eference \$_ } mult_coeff(\$c - 1, @{ \$nck_ref-> }); } } return @sets; } sub nck_with_leftover { my \$k = shift(); return [ [], [ @_ ] ] if \$k <= 0; my @groups; my @leftover; while (@_) { my \$pick = shift(); push @groups, map { unshift(@{ \$_-> }, \$pick); unshift(@{ \$_-> }, @leftover); \$_ } nck_with_leftover(\$k - 1, @_); push @leftover, \$pick; } return @groups; } use Data::Dumper; my @results = mult_coeff(3, qw(a b c d e)); print Dumper \@results;