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;
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.
|
