Daniel Standage - 1 year ago 53

Perl Question

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`

`AB != BA`

`AA`

- Give a breakdown and explanation of how the first algorithm works.
- De-obfuscate the code so that the meaning is clearer.
- Point me toward another example that is clearer.

Thanks!

Answer Source

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.