Keep It Simple, Stupid PerlMonks

### Re: x objects in y containers where all objects are used (multinomial coefficients)

by repellent (Priest)
 on Nov 09, 2009 at 20:42 UTC ( #806018=note: print w/replies, xml ) Need Help??

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;

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://806018]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (3)
As of 2023-03-22 02:16 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Which type of climate do you prefer to live in?

Results (60 votes). Check out past polls.

Notices?