No such thing as a small change PerlMonks

### Comment on

 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;

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

• Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
• Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
• Read Where should I post X? if you're not absolutely sure you're posting in the right place.
• Posts may use any of the Perl Monks Approved HTML tags:
a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
• You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
 For: Use: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?

Create A New User
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (3)
As of 2018-11-21 06:20 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My code is most likely broken because:

Results (237 votes). Check out past polls.

Notices?