3

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

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

谢谢！

4

2 回答 2

4

您可以使用Algorithm :: Combinatorics中的 variables_with_repetition（它还提供了一个基于迭代器的接口），但如果您只需要一个列表，这是一个相当简单的递归算法：

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

于 2011-01-19T15:45:26.200 回答
1

我查看了您提到的页面上的第一段代码：

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会被调用 3 次。第二次调用它将返回@result，即包含对的列表。该列表中的每个项目都将与初始字符集的每个字符连接。

好的，我希望这是有道理的。如果有什么不清楚的地方，请询问。

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

于 2011-01-19T16:51:56.427 回答