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->[0] } ]); # clone r
+eference
$_
} mult_coeff($c - 1, @{ $nck_ref->[1] });
}
}
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(@{ $_->[0] }, $pick);
unshift(@{ $_->[1] }, @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;
