1

ヒープのアルゴリズム順列に基づいて繰り返される文字列をカウントする割り当てがあります。最初にやりたいことは、スワップされた文字列を出力することです。ジェイクの回答からこのコードを見つけました この関数の出力は、交換された文字列です。

function permAlone(string) {

var arr = string.split(''),   // Turns the input string into a letter array.
          permutations = []; // results

function swap(a, b) {  
debugger; // This function will simply swap positions a and b inside the input array.
var tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}

function gen(n) {   
  debugger;
  if (n === 1) {  
  var x =arr.join('');
  permutations.push(x);  
  } else {
  for (var i = 0; i != n; i++) { // how does this loop executes within the call stack?  
    gen(n - 1);
    debugger;
    swap(n % 2 ? 0 : i, n - 1); // i don't understand this part. i understand the swap function, but I don't get how indexes are swapped here
  }   
 }
}
 gen(arr.length);
 return permutations;
}
permAlone('xyz'); // output -> ["xyz","yxz","zxy","xzy","yzx","zyx"]

デバッガーで試してみましたが、まだ何が起こっているのかわかりません。

4

1 に答える 1

3

私はあなたが何を意味するのか分かりません

ループ内のこのコード内の再帰を理解する

アルゴリズムを再帰バージョンではなくループ形式で見たい場合は、ここのウィキペディア ページで疑似コードで並べて見ることができます。

コード内の質問について:

このループはコール スタック内でどのように実行されますか?

コール スタックを参照するのは正しいことです。これは再帰に関する一般的な質問です。再帰がスタックでどのように機能するかを理解していない場合は、java で階乗計算を使用した再帰呼び出しを示すこの非常に素晴らしくシンプルなビデオを参照できます (4:00 頃から開始)。

あなたが見ている行は、再帰関数の他の行と何ら変わりはありません。まず、i を定義し、それに値 0 を割り当てます。for ループの条件を満たすかどうかのチェックを続けます。そうであれば、ループにステップインし、再帰呼び出しであるループ内の最初の行を実行します。再帰呼び出しの内部には、ローカル変数であるため、再帰呼び出しを実行する前に定義した i 変数を知らない新しいスタック フレームがあります。そのため、新しい呼び出しでループに到達したら、新しい変数 i を定義し、最初に 0 を割り当て、このスタック フレーム/呼び出しインスタンスでループが繰り返されるにつれて値をインクリメントします。この呼び出しが終了すると、スタック フレームを削除し、i=0 のままである前のスタック フレーム (開始したフレーム) に戻り、次の行に進みます。関数は変数と同じスコープ (関数 permAlone 内) で定義されているため、すべての呼び出しは arr 変数と permutations 変数にアクセスできます。そのため、各呼び出し内では、スタック フレームに関係なく、それらに加えられた変更は次のようになります。同じインスタンスに作成されました。そのため、順列に対して行われるすべてのプッシュが既存の結果に追加され、関数が最後に変数を返すときにそこに表示されます。

この部分がわかりません。スワップ機能は理解できますが、ここでインデックスがどのようにスワップされるのかわかりません

ここではインデックスは交換されません。これは、正しいインデックスを使用してスワップ関数を呼び出すだけです。

swap(n % 2 ? 0 : i, n - 1);

ただです

swap(a, b);

と

a = n% 2 ? 0 : i;
b = n - 1;

そのa部分があなたを混乱させるものである場合、これは条件値の三項演算子の使用です。つまり、状況に応じて異なる方法で評価される式を形成するために使用される記号です。使用は

<<i>boolean epression</i>> ? <<i>value-if-true</i>> : <<i>value-if-false</i>>

上記を評価するには、最初に < boolean expression > が評価されます。値の場合true、式全体が < value-if-true > として評価されます。それ以外の場合、式全体が < value-if-false > として評価されます。

コード自体では、 foraはn % 2ブール式です。js は で割りn、2余りを取ります。残りは または のいずれ1か0です。js は暗黙的にそれらをそれぞれ および に変換しtrueますfalse。したがって、nが奇数の場合は次のようになります

a = 0

そしてもしそれさえあれば

a = i

アルゴリズムが必要とするため。

于 2016-09-09T15:53:44.260 に答える