0

私はプロジェクトに取り組んでいます。Interwebz の順列に関するこのコードを見つけました。独自のコードを記述するための基礎として使用したいと思います。ただし、コードで何が起こっているのかよくわかりません。誰か私に手を貸して、コードが正確に何をしているのか説明してもらえますか?

public void permutations(String prefix, String s) {
    int n = s.length();
    if (n == 0)
        System.out.println(prefix);
    else {
        for(int i = 0; i < n; i++){
           permutations(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, n));
        }
    }
}
4

4 に答える 4

2

p(String prefix, String s)から 1 文字を取り出してs追加し、が空になるprefixまで再帰的に続行します。s

このs.charAt(i), s.substring(0, i) + s.substring(i+1, n)部分は から文字を抽出しsます。s = "Magic!"そしてi = 3、charAt(i) = 'i'、s.substring(0, i) = "Mag"と仮定しs.substring(i+1, n) = c!"ます。それはとMagic!に流れ込みます。次回のループでは+になります。それを行うので、すべての文字のすべての文字が再帰ステップの 1 つで前面に表示されます。iMagc!i = 4cMagi!s

呼び出し階層は次のようになります

                                  / p("ab", "c") - "abc"
                 /- p("a", "bc") x
                /                 \ p("ac", "b") - "acb"
               /
              /                   / p("ba", "c") - "bac"
p("", "abc") x ---- p("b", "ac") x
              \                   \ p("bc", "a") - "bca"
               \
                \                 / p("ca", "b") - "cab"
                 \- p("c", "ab") x
                                  \ p("cb", "a") - "cba"

                 ^-- 1st for loop  ^- 2nd for      ^- 3rd one prints
于 2012-12-06T01:31:18.310 に答える
2

このメソッドpermutationsは、Stringprefixと Stringsをパラメーターとして取り込んでいます。intタイプnは String の長さに設定されていますs。（文字列の長さは、含まれる文字数です）。

次に、if-elseステートメントに進みます。このifステートメントは、 の長さsが 0 の場合、つまりs、空白の文字列であり、情報が含まれていない場合、prefix代わりに文字列をコンソールに出力しているだけです。メソッドはその部分をスキップして、メソッドelseの後のコードを実行しますpermutations。

ifステートメントの条件が満たされない場合はelse、 String の各文字に対して、sその文字を の末尾に追加 (追加) するというステートメントを実行しますprefix。たとえば、prefix元々「hello」だった場合文字が「U」だった場合、 prefix「helloU」になります。のすべての文字の追加が完了したらs、結果を新しいprefix文字列として使用します。

もう 1 つのパラメーターである Stringsについては、文字 0 (含む) から位置の文字 (含まない) までの文字列の一部を取得しますi。文字列インデックスは 0 から始まり、(文字列の長さ - 1) まで続くことに注意してください。また、位置 i + 1 (両端を含む) の文字から String の最後の文字までの String の一部を取得していsます。この結果を新しいs文字列として使用します。

次に、メソッドを再度呼び出し、else条件が満たされた場合、メソッドは新しく定義された文字列で再度実行されます。elseこれは、条件が満たされない時点でメソッドの実行を停止し、コードの次のセクション (存在する場合) に進むまでループを続けます。

于 2012-12-06T00:51:21.053 に答える
1

permutations(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, n));

実は、この順列アルゴリズムは

Switching current character with ith character.

string があるとしますabc。したがって、その順列は次のとおりです。

abc, acb, bac, bca, cab, cba

acbが切り替わっただけbで、プレフィックスが付いcていることがわかります。そして、は切り替わるだけで、プレフィックスが付けられています。abcabcacabacb

次に、同じアイデアを使用して、順列問題を再帰的に解決します。

于 2012-12-06T00:36:46.093 に答える
1

これは、次の 2 つの理由から、非常に紛らわしいコードです。

  1. 引数: この関数は、最初の引数に空の文字列を指定して呼び出す必要があります。prefixたとえば、 のpermutations("", "ab")すべて (両方) の順列を出力するには、"ab".
  2. 2 番目の引数での再帰呼び出し: Javaには y 番目の文字が含まれないことs.substring(0, i) + s.substring(i+1, n)に注意してください。したがって、これは y 番目の文字を削除して渡すことになります。String.substring(x,y)s

forループをステップ実行するとどうなるか考えてみてください。最初の引数は と""連結され"a"、つまり"a"、2 番目の引数sは最初の文字が削除されて になり"b"ます。次の再帰サブコールでは、 にprefixなり"ab"、2 番目の引数は空の文字列になります""。したがって、基本ケースn == 0がヒットし、結果を出力し"ab"ます。

次に、for ループの次の繰り返しに進みますi == 1。ここ"b"で、再帰サブコールの最初の引数と"a"2 番目の引数を渡します。次の再帰サブコールでは、andが 0 になるため、基本ケースが再び print になりprefixます。"ba"s.length"ba"

それは賢いですが、不可解です。

于 2012-12-06T01:01:03.437 に答える