0

String を可能なすべての組み合わせに並べ替える方法を示す本の例に取り組んできましたが、一般的なプログラミングの初心者であるため、コードがどのように機能するかを実際に理解することはできません!

誰かが私が提供したコードを分析して、すべてが何をどのように行うのかを完全に説明してもらえますか?

どうもありがとう、

アレックス。

class PermuteString{
    String word;
    int index;
    PermuteString substringGenerator;
    public PermuteString(String s){
        word = s;
        index = 0;
        if(s.length() > 1){
              substringGenerator = new PermuteString(s.substring(1));
    }
}

public String nextPermutation(){
    if(word.length() == 1){
        ++index;
        return word;
    }
    else{
        String r = word.charAt(index) + substringGenerator.nextPermutation();
        if(!substringGenerator.morePermutations()){
            ++index;
            if(index < word.length()){
                String tailString = word.substring(0, index) + word.substring(index + 1);
                substringGenerator = new PermuteString(tailString);
            }
        }
        return r;
    }
}

public boolean morePermutations(){
    return index < word.length();
}

}

public class PermuteStringDemo {
public static void main(String[] args){
    PermuteString p = new PermuteString("opyn");
    while(p.morePermutations())
        System.out.println(p.nextPermutation());
}
}
4

2 に答える 2

2

順列を生成するには、通常 2 つの方法があります

  1. ランキングとアンランキング
  2. 増分変更方法

このルーチンは増分変更方式を使用します。基本的に、要素の順序 (最初と同じ順序) を選択し、1 つの要素をシャッフルしてオプションのツリーを上下に移動し、その下で必要なサブ順列を再帰的に生成します。

permutation(everything) expands to

(select 1) + permutation(everything but 1)
(select 2) + permutation(everything but 2)
(select 3) + permutation(everything but 3)
...
(select n) + permutation(everything but n)

and

permuation(one item) expands to
(select item)

これは、ネストされたクラスmorePermutations()に要素が 1 つしかない場合に false を返すによって制御されます。PermuteString

に 2 つ以上の文字がある場合、 は選択された項目PermuteStringをindex追跡し、PermuteStringインデックスが移動されると新しいサブが構築されます。

次の順列を要求されるPermuteStringと、子に「次の」順列がないことを文字列が検出するまで、リクエストはネストされた s を下に移動し、親がインデックスを更新し、前の子を現在の新しい子と交換します。 「新しい」indexキャラクターだけが欠けています。

(完全を期すために、ランキングと非ランキングの概要を説明します)

ランキングとランキング解除は異なる働きをします。特定のサイズのすべての可能な順列の数を知っているので、そのサイズ内の「インデックス」への順列のマップを作成します。次に、そのインデックスから値への逆マップを作成します。高レベルの例は次のようになります

the entire map for 3 items (6 permutations) would look like

(a, b, c) <=> 0
(a, c, b) <=> 1
(b, a, c) <=> 2
(b, c, a) <=> 3
(c, a, b) <=> 4
(c, b, a) <=> 5

(a, b, c) => 0
to find the next, just add one
0 + 1 => 1
1 => (a, c, b)

メモリ内にマップを維持せずにマッピング解除順列をマッピングするための正式な数学的手段がありますが、インデックスが非常に急速に大きくなり、数が MAX_INT を超えると問題が発生することが多いため、これらは使用されないことがよくあります。

于 2013-08-06T16:01:57.573 に答える