algorithm - 如何在 Perl 中生成长度为 k 的所有有序组合？

Question

我需要一个子程序，给定一组字符，将生成这些长度为 k 的字符的所有可能组合。顺序很重要并且允许重用，因此如果 k = 2 那么 AB != BA 和 AA 是一个选项。我找到了 some working examples on PerlMonks ，但不幸的是，它们是代码高尔夫，对我来说并不容易全神贯注。有人可以执行以下一项或多项操作吗？

1. 对第一个算法的工作原理进行分解和解释。
2. 对代码进行去混淆处理，使含义更清晰。
3. 给我指出另一个更清楚的例子。

谢谢!

Answer 1

您可以使用 variations_with_repetition来自 Algorithm::Combinatorics (它还提供了一个基于迭代器的接口(interface))，但如果你只需要一个列表，这是一个相当简单的递归算法:

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);

这与代码高尔夫球手使用的算法基本相同，但我使用的是 for 循环而不是嵌套 map。此外，我每个级别只递归一次(代码高尔夫是关于最小化源代码，而不是运行时)。

任何递归函数都可以转换为迭代函数，这通常会减少其开销。这个相当简单:

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

此版本处理 $k == 0 情况，而原始版本没有。