在Perl中，我该如何生成一个列表的所有可能组合？

Question

我有一个列表文件，需要生成一个比较每一行的新文件。例如，我的文件内容如下：

AAA  
BBB  
CCC  
DDD  
EEE

我想让最终的列表看起来像这样：

AAA  BBB  
AAA  CCC  
AAA  DDD  
AAA  EEE  
BBB  CCC  
BBB  DDD  
BBB  EEE  
CCC  DDD  
CCC  EEE  
DDD  EEE

我正在尝试在Perl中完成这个任务，但是遇到了一些问题。我知道需要创建一个数组，然后对其进行分割，但是之后我就有些困惑了。

- user1352084

---

请发布你目前的代码。 - tuxuday

Answer 1

使用Algorithm::Combinatorics。 基于迭代器的方法优于一次性生成所有内容。

#!/usr/bin/env perl

use strict; use warnings;
use Algorithm::Combinatorics qw(combinations);

my $strings = [qw(AAA BBB CCC DDD EEE)];

my $iter = combinations($strings, 2);

while (my $c = $iter->next) {
    print "@$c\n";
}

输出：

AAA BBB
AAA CCC
AAA DDD
AAA EEE
BBB CCC
BBB DDD
BBB EEE
CCC DDD
CCC EEE
DDD EEE

- Sinan Ünür

Answer 2

使用递归很容易编写此代码。

以下是示例代码。

use strict;
use warnings;

my $strings = [qw(AAA BBB CCC DDD EEE)];

sub combine;

print "@$_\n" for combine $strings, 5;

sub combine {

  my ($list, $n) = @_;
  die "Insufficient list members" if $n > @$list;

  return map [$_], @$list if $n <= 1;

  my @comb;

  for my $i (0 .. $#$list) {
    my @rest = @$list;
    my $val  = splice @rest, $i, 1;
    push @comb, [$val, @$_] for combine \@rest, $n-1;
  }

  return @comb;
}

---

编辑

抱歉 - 我生成的是排列而不是组合。

这段代码是正确的。

use strict;
use warnings;

my $strings = [qw(AAA BBB CCC DDD EEE)];

sub combine;

print "@$_\n" for combine $strings, 2;

sub combine {

  my ($list, $n) = @_;
  die "Insufficient list members" if $n > @$list;

  return map [$_], @$list if $n <= 1;

  my @comb;

  for (my $i = 0; $i+$n <= @$list; ++$i) {
    my $val  = $list->[$i];
    my @rest = @$list[$i+1..$#$list];
    push @comb, [$val, @$_] for combine \@rest, $n-1;
  }

  return @comb;
}

输出

AAA BBB
AAA CCC
AAA DDD
AAA EEE
BBB CCC
BBB DDD
BBB EEE
CCC DDD
CCC EEE
DDD EEE

- Borodin

Answer 3

看一下Math::Combinatorics - 在列表中执行组合和排列。

从CPAN复制的示例：

use Math::Combinatorics;

  my @n = qw(a b c);
  my $combinat = Math::Combinatorics->new(count => 2,
                                          data => [@n],
                                         );

  print "combinations of 2 from: ".join(" ",@n)."\n";
  print "------------------------".("--" x scalar(@n))."\n";
  while(my @combo = $combinat->next_combination){
    print join(' ', @combo)."\n";
  }

  print "\n";

  print "permutations of 3 from: ".join(" ",@n)."\n";
  print "------------------------".("--" x scalar(@n))."\n";
  while(my @permu = $combinat->next_permutation){
    print join(' ', @permu)."\n";
  }

  output:
combinations of 2 from: a b c
  ------------------------------
  a b
  a c
  b c

  permutations of 3 from: a b c
  ------------------------------
  a b c
  a c b
  b a c
  b c a
  c a b
  c b a

- Nikhil Jain

---

为什么不使用问题中的示例数据？ - daxim

Answer 4

我进行了以下Perl模块的基准测试:

1. Math::Combinatorics
2. Algorithm::Combinatorics
3. Cmb

基准测试包括执行OP要求的内容，即组合2个项目，但将单词集合从原始请求的5个(AAA BBB CCC DDD EEE)增加到10,000个。

Math::Combinatorics的测试脚本

#!/usr/bin/env perl
use strict; use warnings;
use Math::Combinatorics;
my $strings = [qw(AAA BBB CCC DDD EEE) x 2000];
my $iter = new Math::Combinatorics (count => 2, data => $strings);
while (my @c = $iter->next_combination) {
    print "@c\n";
}

这产生了每秒约53,479个组合。

Algorithm::Combinatorics的测试脚本

#!/usr/bin/env perl
use strict; use warnings;
use Algorithm::Combinatorics qw(combinations);
my $strings = [qw(AAA BBB CCC DDD EEE) x 2000];
my $iter = combinations($strings, 2);
while (my $c = $iter->next) {
    print "@$c\n";
}

这产生了每秒约861,982个组合。

Cmb的测试脚本

#!/usr/bin/env perl
use strict; use warnings;
use Cmb;
my $strings = [qw(AAA BBB CCC DDD EEE) x 2000];
my $cmb = new Cmb { size_min => 2, size_max => 2 };
$cmb->cmb_callback($#$strings + 1, $strings, sub {
    print "@_\n";
    return 0;
});

这产生了大约每秒2,940,882种组合。

但如果您只需要打印组合，Cmb实际上可以比上述方法更快地完成。

#!/usr/bin/env perl
use strict; use warnings;
use Cmb;
my $strings = [qw(AAA BBB CCC DDD EEE) x 2000];
my $cmb = new Cmb { size_min => 2, size_max => 2 };
$cmb->cmb($#$strings + 1, $strings);

这产生了大约每秒3,333,000个组合。 基准测试是在CentOS Linux release 7.7.1908 (Core)下，使用Perl 5.16.3在Intel(R) Xeon(R) CPU E5-2699 v4 @ 2.20GHz上运行，内核版本为3.10.0-1062.1.1.el7.x86_64 x86_64，使用dpv。

- user3527600

Answer 5

这是一个使用 glob 的 hack：

my @list = qw(AAA BBB CCC DDD EEE);

for my $i (0..$#list-1) {
    print join "\n", glob sprintf "{'$list[$i] '}{%s}",
          join ",", @list[$i+1..$#list];
    print "\n";
}

输出：

AAA BBB
AAA CCC
AAA DDD
AAA EEE
BBB CCC
BBB DDD
BBB EEE
CCC DDD
CCC EEE
DDD EEE

附言：您可能希望使用{{link1：Text::Glob::Expand}}或{{link2：String::Glob::Permute}}模块，而不是普通的glob()，以避免匹配当前工作目录中的文件的注意事项。

- Eugene Yarmash

---

使用 glob 技巧时，应注意其可能失败的各种注意事项。 - daxim

Answer 6

1. 取第一个字符串
2. 从下一个位置到末尾遍历数组
   1. 将下一个字符串附加到原始字符串
3. 取下一个字符串并返回步骤2

- msam

Answer 7

这样怎么样：

#!/usr/bin/perl
use strict;
use warnings;
use Data::Dump qw(dump);

my @in = qw(AAA BBB CCC DDD EEE);
my @list;
while(my $first = shift @in) {
    last unless @in;
    my $rest = join',',@in;
    push @list, glob("{$first}{$rest}");
}
dump @list;

输出：

(
  "AAABBB",
  "AAACCC",
  "AAADDD",
  "AAAEEE",
  "BBBCCC",
  "BBBDDD",
  "BBBEEE",
  "CCCDDD",
  "CCCEEE",
  "DDDEEE",
)

- Toto

---

使用glob技巧时，应始终注意它可能失败的各种注意事项。 - daxim

@daxim：你是指在当前工作目录中匹配文件的“副作用”吗？如果是这样，那么这难道不是完全安全的吗，因为他没有使用?、[]或*吗？ - flesk

所有这些。我现在很烦恼，应该将注意事项清楚地列出作为答案的一部分，而不是作为评论附加的修辞问题，能见度低。这不是“副作用”，它确实发生了，模态化这个词是错误的。这是不安全的：显然，用户在问题中提供了虚构/匿名数据，并且在真实世界条件下将会遭受到不好的惊喜。SO答案应该努力避免让人们失败，他们应该始终意识到微妙和风险；鉴于此，我现在已经对这个答案进行了投票，以给M42改进的动力。--继续： - daxim

如果仅仅是因为文档更好，并且它们在内存数据结构上执行操作，而不受外部因素（如shell或当前目录中的内容）的影响，我建议使用Text::Glob::Expand或String::Glob::Permute代替普通的 glob。 - daxim

@daxim：这是一个很好的观点。引用副作用只是个玩笑：我同意SO不是教授这些技巧的最佳场所。 - flesk