10

私は、金曜日の入学願書の実際の順列アルゴリズムに頭を悩ませて (ついに) 一日を費やしました。Heap のアルゴリズムは、私にとって最もシンプルでエレガントに思えました。

ここにその例があります：http://en.wikipedia.org/wiki/Heap%27s_algorithm

 function permutationArr(num) { 
    var str = num.toString();
    var arr = str.split('');
    var permutations = [];   
    function getPerm(arr,n){   
        var localArr = arr.slice(0);
        var i;
        var swap;
        var temp; 
        if(n==1){
            permutations.push(localArr.toString());
            return;
        }
        for(i=0;i<n;i++){
            getPerm(localArr,n-1);    
            swap = (n%2 ? i: 0);
            temp = localArr[swap];
            localArr[swap] = localArr[n-1];
            localArr[n-1] = temp;    
        }
    }    
    getPerm(arr,arr.length);
    console.log(permutations);
    return;    
}    
permutationArr(1234);

最終的な順列配列のログは次のとおりです。

 ["1,2,3,4", "1,3,2,4", "4,2,3,1", "4,3,2,1", "4,1,3,2", "4,3,1,2", "1,,3,4,2", "1,3,,4,2", "4,,3,1,2", "4,3,,1,2", "4,1,3,,2", "4,3,1,,2", "1,2,3,4,", "1,3,2,4,", "4,2,3,1,", "4,3,2,1,", "4,1,3,2,", "4,3,1,2,", "1,,3,4,2", "1,3,,4,2", "4,,3,1,2", "4,3,,1,2", "4,1,3,,2", "4,3,1,,2"]

最初の 12 個の順列がうまくいき、その後不思議なことに「,」が追加され、最初の 12 個の順列が繰り返されます。私は困惑しています。

編集：上記は、コメントが役立つと言ったことを考慮して更新されたコードです。まだ順列の半分しか取得していません。

4

3 に答える 3

12

n問題は、使用すべき場所でインデックスを使用する以外にn - 1、呼び出し間で配列をコピーする必要があると想定していることです (つまり、不変の動作)。

アルゴリズムは、各再帰ステップで配列が常に同じであると想定しているため、JavaScript がスコープを処理する方法のおかげで、コードを大幅に簡素化できます。

function permutationArr(num) 
{ 
  var arr = (num + '').split(''),
  permutations = [];   

  function swap(a, b)
  {
    var tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
  }

  function generate(n) {
    if (n == 1) {
      permutations.push(arr.join());
    } else {
      for (var i = 0; i != n; ++i) {
        generate(n - 1);
        swap(n % 2 ? 0 : i, n - 1);
      }
    }
  }

  generate(arr.length);
  return permutations;
}    

console.log(permutationArr(1234));

出力

["1,2,3,4", "2,1,3,4", "3,1,2,4", "1,3,2,4", "2,3,1,4", "3,2,1,4", "4,2,3,1",
 "2,4,3,1", "3,4,2,1", "4,3,2,1", "2,3,4,1", "3,2,4,1", "4,1,3,2", "1,4,3,2", 
 "3,4,1,2", "4,3,1,2", "1,3,4,2", "3,1,4,2", "4,1,2,3", "1,4,2,3", "2,4,1,3", 
 "4,2,1,3", "1,2,4,3", "2,1,4,3"]
于 2014-12-18T05:54:06.873 に答える