首页 文章

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

提问于
浏览 次
16

我有一个带有列表的文件，需要创建一个文件，将每行与另一行进行比较 . 例如，我的文件有这个：

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中这样做，这是第一次，我遇到了一些麻烦 . 我知道你需要制作一个数组，然后拆分它，但之后我遇到了一些麻烦 .

arrays perl combinations combinatorics

6 回答

  • 29

    使用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
    回复于
  • 0

    使用递归来编写它是很简单的 .

    此代码示例演示 .

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

    Edit

    我道歉 - 我正在产生排列而不是组合 .

    这段代码是正确的 .

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

    output

    AAA BBB
AAA CCC
AAA DDD
AAA EEE
BBB CCC
BBB DDD
BBB EEE
CCC DDD
CCC EEE
DDD EEE
    回复于
  • 0

    看看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
    回复于
  • 7

    • 取第一个字符串

    • 从下一个位置到结束迭代数组

    • 将下一个字符串附加到原始字符串

    • 接下一个字符串并返回第2步

    回复于
  • 0

    怎么样：

    #!/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;

    output:

    (
  "AAABBB",
  "AAACCC",
  "AAADDD",
  "AAAEEE",
  "BBBCCC",
  "BBBDDD",
  "BBBEEE",
  "CCCDDD",
  "CCCEEE",
  "DDDEEE",
)
    回复于
  • 8

    这是使用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

    附：您可能希望使用Text::Glob::Expand或String::Glob::Permute模块而不是普通 glob() 来避免在当前工作目录中匹配文件的警告 .

    回复于

相关问题