Daniel Standage - 4 months ago 9
Perl Question

# How can I generate all ordered combinations of length k in Perl?

I need a subroutine that, given a set of characters, will generate all possible combinations of those characters of length k. Order matters and reuse is allowed, so if

`k = 2`
then
`AB != BA`
and
`AA`
is an option. I found some working examples on PerlMonks, but unfortunately they are code golf and not easy for me to wrap my mind around. Can someone please do one or more of the following?

1. Give a breakdown and explanation of how the first algorithm works.

2. De-obfuscate the code so that the meaning is clearer.

3. Point me toward another example that is clearer.

Thanks!

You can use variations_with_repetition from Algorithm::Combinatorics (which also provides an iterator-based interface), but if you just need a list, this is a fairly simple recursive algorithm:

``````sub ordered_combinations
{
my (\$data, \$k) = @_;

return @\$data if \$k == 1;

my @previous = ordered_combinations(\$data, \$k-1);

my @results;
for my \$letter (@\$data) {
push @results, map { \$letter . \$_ } @previous;
}

return @results;
} # end ordered_combinations

print "\$_\n" for ordered_combinations([qw(a b c)], 3);
``````

This is basically the same algorithm the code golfers are using, but I'm using a `for` loop instead of nesting `map`. Also, I recurse only once per level (code golf is about minimizing source code, not runtime).

Any recursive function can be converted to an iterative one, which usually reduces its overhead. This one is fairly simple:

``````sub ordered_combinations
{
my (\$data, \$k) = @_;

return if \$k < 1;

my \$results = \$data;

while (--\$k) {
my @new;
for my \$letter (@\$data) {
push @new, map { \$letter . \$_ } @\$results;
} # end for \$letter in @\$data

\$results = \@new;
} # end while --\$k is not 0

return @\$results;
} # end ordered_combinations
``````

This version handles the `\$k == 0` case, which the original did not.