如何在Perl中生成長度爲k的所有有序組合？

Question

我需要一個子程序，給定一組字符，將生成長度爲k的所有可能的字符組合。訂單事項和重用是允許的，所以如果k = 2然後AB != BA和AA是一個選項。我發現some working examples on PerlMonks，但不幸的是，他們代碼高爾夫球，並不容易我纏繞我的腦海。有人可以請做一個或多個以下？

1. 給出第一個算法如何工作的細分和解釋。
2. 去混淆代碼，使意思更清晰。
3. 指向另一個更清晰的例子。

謝謝！

Answer 1

您可以使用從Algorithm::Combinatoricsvariations_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情況下，原來沒有。

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'（$炭），從而是（ 'AA'， 'AB'）。在foreach循環的下一輪中，與$char = B相同，其將設置爲（'BA'，'BB'）。

在每一輪的內容被推入結果列表，因此@result最終包含所有可能的組合。

如果你想得到三胞胎而不是成對，你很明顯會從$number = 3開始，並且combinations將被調用三次。第二次調用它將返回@result，即一個包含對的列表。該列表中的每個項目都將與初始字符集的每個字符連接。

好的，我希望這是有道理的。如果事情沒有明確，請提問。

編輯：請參閱以下ysth的評論。