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

Question

我需要一个子程序，给定一组字符，将生成长度为k的所有可能的字符组合。顺序很重要且允许重复使用，因此如果 k = 2，则 AB != BA 且 AA 是一种选项。我在PerlMonks上找到了一些工作示例，但不幸的是，它们都是代码高尔夫，对我来说很难理解。有人可以做以下一项或多项吗？

1. 解释和解析第一个算法的工作原理。
2. 揭秘代码以使含义更加清晰。
3. 指向另一个更清晰的示例。

谢谢！

- Daniel Standage

Answer 1

你可以使用重复排列，它来自于算法：组合数学（它还提供了一种基于迭代器的接口），但如果你只需要一个列表，那么这是一个相当简单的递归算法：

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 的情况，而原始版本没有。

- cjm

Answer 2

我看了一下你提到的页面上的第一段代码：

sub c{my$n=-1+shift;$n?map{my$c=$_;map$c.$_,c($n,@_)}@_:@_}

我将其展开以使其更易读；此外，我对其进行了一些更改以使其更清晰（参见combinations）：

#!/usr/bin/perl

use strict;
use warnings;

sub c {
   my $n=-1+shift;
   $n ? map{
             my $c = $_;
             map $c . $_ , c($n ,@_)
           } @_
   : @_;
}

sub combinations {
   my $number = shift; # remove the first item from @_
   my @chars  = @_;    # the remainder of @_

   $number --; # decrement $number, so that you will eventually exit
               # from this recursive subroutine (once $number == 0)

   if ($number) { # true as long as $number != 0 and $number not undef

      my @result;

      foreach my $char (@chars) {
         my @intermediate_list = map { $char . $_ } combinations($number, @chars);
         push @result, @intermediate_list;
      }

      return @result; # the current concatenation result will be used for creation of
                      # @intermediate_list in the 'subroutine instance' that called 'combinations'
   }
   else {
      return @chars;
   }
}

print join " ", combinations(2, "A", "B");
print "\n";
print join " ", c(2, "A", "B");
print "\n\n";
print join " ", combinations(3, "A", "B");
print "\n";
print join " ", c(3, "A", "B");
print "\n";

这两个版本的工作方式相同，它们产生的输出完全相同：

AA AB BA BB
AA AB BA BB

AAA AAB ABA ABB BAA BAB BBA BBB
AAA AAB ABA ABB BAA BAB BBA BBB

我在代码中包含了一些注释，但也许需要更详细的解释？好吧，这里有一个例子来说明事情是如何工作的：假设我们有两个项目，“A”和“B”，我们想要获取这些项目中任意2个的所有可能组合。在这种情况下，$number 最初将等于2（因为我们想要获取成对的项目），@chars 将等于 ('A', 'B')。

第一次调用 combinations 时，$number 被减少到1，因此满足 if 条件，我们进入 foreach 循环。这首先将 $char 设置为“A”。然后它调用 combinations(1, ('A', 'B'))。由于每次调用子程序时都会将 $number 减少，因此在这个“子例程”中，$number 为0，因此子程序只返回（'A'，'B'）。因此：

@intermediate_list = map { $char . $_ } ('A', 'B'); # $char eq 'A'

map然后将'A'和'B'连接到每个'A'($char)之后，因此@intermediate_list是('AA'，'AB')。在下一轮的foreach 循环中，使用$char = B执行相同操作，将@intermediate_list设置为('BA'，'BB')。

在每一轮中，@intermediate_list的内容都被推入结果列表中，因此@result最终包含所有可能的组合。

如果要获得三元组而不是二元组，则显然需要以$number = 3开始，并且会调用三次combinations。第二次调用它时，它将返回@result，即包含一对的列表。该列表中的每个项将与初始字符集的每个字符连接。

好的，我希望这讲得清楚。如有疑问，请提出。

编辑：请参见ysth下面的评论。

- canavanin

---

“will be called three times” 应该翻译为 “将递归到深度为3”，实际上会有更多的调用（除非你只有一个字母...）。 - ysth

@ysth 好的，那很有道理。我以前从未使用过递归子程序，因此不熟悉这些术语。感谢指出错误！ - canavanin