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

Question

我需要一个子例程，给定一组字符，它将生成长度为k的字符的所有可能组合。Order很重要，并且允许重用，所以如果k = 2，那么AB != BA和AA是一个选项。我找到了关于PerlMonks的几个工作示例，但不幸的是，它们是代码高尔夫，对我来说很难将我的注意力集中起来。有人能做以下一项或多项吗？

1. 给出一个细分和解释第一个算法是如何工作的。
2. 去混淆代码，使其含义更清晰。
3. 告诉我另一个更清楚的例子。

谢谢!

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案例，而原始版本没有。

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"，我们想得到其中两个项目的所有可能组合。在这种情况下，$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评论。