Perlで長さkのすべての順序付けられた組み合わせを生成するにはどうすればよいですか？

Question

私はサブルーチンが必要です。サブルーチンは、文字セットを与えられたときに、長さkのそれらの文字のすべての可能な組み合わせを生成するサブルーチンを必要とします。注文事項と再利用が許可されているので、k = 2の場合はAB != BAとAAのオプションです。私はsome working examples on PerlMonksを見つけましたが、残念ながら彼らはコードゴルフであり、私の心を包み込むのは簡単ではありません。誰かが次のうちの1つ以上をしてください。

1. 最初のアルゴリズムの仕組みを説明してください。
2. 意味が明確になるようにコードの難読化を解除します。
3. もう少し明確な例を挙げてください。

ありがとう！

Answer 1

あなたは（また、反復子ベースのインターフェースを提供する）Algorithm::Combinatoricsからvariations_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); 

これは基本的に同じアルゴリズムでありますコードゴルファーが使用していますが、mapの代わりにforループを使用しています。また、レベルごとに1回だけ繰り返されます（コード・ゴルフは、ランタイムではなくソース・コードの最小化に関するものです）。

任意の再帰関数を反復関数に変換できます。反復関数は通常、オーバーヘッドを削減します。この1は非常に簡単です：

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,@_)}@_:@_} 

を。私はいくつかを含め

AA AB BA BB 
AA AB BA BB 

AAA AAB ABA ABB BAA BAB BBA BBB 
AAA AAB ABA ABB BAA BAB BBA BBB 

：両方のバージョンが同じように動作し、彼らはまったく同じ出力を生成

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

：また、私はそれをより明確にするために、それにいくつかの変更を（combinationsを参照してください）行いましたコード内のコメントですが、おそらく長めの説明が順番です！さて、物事の仕方を説明する例があります：「A」と「B」という2つのアイテムがあり、これらのアイテムのうち2つをすべて組み合わせたいとします。その場合、$numberは最初は2になり（ペアを取得したいので）、@charsは('A', 'B')に等しくなります。

初めてcombinationsが呼び出され、$numberは、このようにif条件が満たされ、1に減らされ、我々は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）と連結し、それぞれ、こうして（ 'AA'、 'AB'）です。 foreachループの次のラウンドでは、同じことが$char = Bで行われ、を（ 'BA'、 'BB'）に設定します。

各ラウンドでの内容が結果リストにプッシュされます。したがって、@resultに最終的にすべての可能な組み合わせが含まれます。

ペアの代わりにトリプレットを取得する場合は、明らかに$number = 3で始まり、combinationsが3回呼び出されます。 2回目に呼び出されると、@result、つまりペアを含むリストが返されます。そのリストの各項目は、最初の文字セットの各文字と連結されます。

これは意味があると思います。何かが明確になっていない場合はお尋ねください。

EDIT：下記のysthさんのコメントをご覧ください。