How can I generate all ordered combinations of length k in 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 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!

Answer 1

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.