Javaの組み合わせの組み合わせを見つけるための再帰的アルゴリズム

Question

Javaのすべての組み合わせを指定したセット（文字列または整数の配列）を見つける方法の例をいくつか探し出そうとしていました。そして私は、このコードの一部に出くわしてきた（http://introcs.cs.princeton.edu/java/23recursion/Combinations.java.htmlで見つかった私はここで唯一の関連部品をコピーした。。）：

// print all subsets of the characters in s 
public static void comb1(String s) { comb1("", s); } 

// print all subsets of the remaining elements, with given prefix 
private static void comb1(String prefix, String s) { 
    if (s.length() > 0) { 
     System.out.println(prefix + s.charAt(0)); 
     comb1(prefix + s.charAt(0), s.substring(1)); 
     comb1(prefix,    s.substring(1)); 
    } 
} 

// read in N from command line, and print all subsets among N elements 
public static void main(String[] args) { 
    int N = Integer.parseInt(args[0]); 
    String alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"; 
    String elements = alphabet.substring(0, N); 

    // using first implementation 
    comb1(elements); 
    System.out.println(); 
} 

しかし、私は実際にそれがどのように動作するか理解していません。誰かが説明する気になる？

Answer 1

Javaプログラムはmainで始まります。これは整数でなければならない引数をとります。ユーザがjavaをタイプし、プログラム名を3とすると、Nは3に設定されます。これはアルファベットの最初のN文字を切り離して要素に配置するために使用されます。 （この例では、abc）。次に、comb1（abc）、つまりパブリックcomb1が最初にリストされます。

次のcomb1は、2つの引数、つまり空の文字列abcを持つprivate comb1を呼び出します。

これで再帰が開始されます。プライベートcomb1は接頭辞と文字列を取ります（最初の場合は空の文字列でabc）。文字列が空でない場合、それ：

1. 再帰的
2. コール自体接頭+新しい文字列として新たなプレフィックス及び残部としての第1のチャー及び
3. コール自体と、再帰的にと最初の文字を印刷し新しい接頭辞と同じ接頭辞と、最初の文字を除くすべての接頭辞を新しい文字列として返します。

（多くの人が...少し震え、それを凝視、上のハングアップ、コンピュータであり、意味が来るだろうのはここです。）

(Top level) 
comb1("", "abc") -> *1* a *2* comb1("a", "bc") *3* comb1("", "bc") 

(Second level) 
comb1("a", "bc") -> *1* ab *2* comb1("ab", "c") *3* comb1("a", "c") 
comb1("", "bc") -> *1* b *2* comb1("b", "c") *3* comb1("", "c") 

(Third level) 
comb1("ab", "c") -> *1* abc *2* comb1("abc", "") *3* comb1("ab", "") 
comb1("a", "c") -> *1* ac *2* comb1("a", "") *3* comb1("a", "") 

comb1("b", "c") -> *1* bc *2* comb1("bc", "") *3* comb1("b", "") 
comb1("", "c") -> *1* c *2* comb1("c", "") *3* comb1("", "") 

(Fourth level) 
comb1("ab", "") -> (immediate return, ending recursion) 
comb1("a", "") -> (immediate return, ending recursion) 
comb1("b", "") -> (immediate return, ending recursion) 
comb1("", "") -> (immediate return, ending recursion) 

Answer 2

与えられたセットのすべての組み合わせを作成するのは本当に簡単です。 N個の要素があり、それぞれの要素に要素が存在するかどうかは関係なく、2^Nの組み合わせです。その再帰関数はまさにそれを行います。それはそのリストから各要素を取り出し、それを含む組み合わせを作成し、それを持たない組み合わせを作成します。注：空の組み合わせは印刷されません。

まだ解明されていない場合は、短いテスト文字列（例：3文字）を作成し、デバッガを起動して動作を確認します。