私のコードがすべての順列を2回押すのはなぜですか？

Question

なぜ私のコードがすべての順列を2回押しているのか混乱しています。助けてください。私は、ヒープのアルゴリズムを使用しています：

var regex = /(.)\1+/g; 

function permAlone(str) { 
    var newArray = str.split(''); 
    var n = newArray.length; 
    var permutations = []; 
    var tmp; 

    function swap(index1, index2) { 
    tmp = newArray[index1]; 
    newArray[index1] = newArray[index2]; 
    newArray[index2] = tmp; 
    } 

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

     generate(n-1, newArray); 
    }  
    } 

    generate(n, newArray); 
    return permutations; 
}  

permAlone('aab'); 

返される配列は次のとおりです。

["aab", "aab", "aab", "baa", "baa", "aba", "aba", "aba", "baa", "baa"] 

あなたが見ることができるように、順列は各事を意図したよりも多くの回登場しています。すべてのヘルプは

Answer 1

コードは少し複雑だ素晴らしいことだし、それは再帰与えられた追跡するのは難しいのですが、あなたが望むすべてが唯一の一意の値を持つ配列がある場合、あなたは、単に結果の配列に次のコードを適用することができます。

function stripDuplicates(input) { 
    if (!input || typeof(input) !== 'object' || !('length' in input)) { 
     throw new Error('input argument is not array.'); 
    } 

    var newArray = []; 
    for (var i = 0; i < input.length; i++) { 
     if (newArray.indexOf(input[i]) === -1) { 
      newArray.push(input[i]); 
     } 
    } 

    return newArray; 
} 

これは、命令的ではなく機能的に行うこともできますが、実際は最適化の問題よりも優先されます。

Bálintは、結果をSetに変換し、SetをArrayに戻すと、自動的に重複を取り除くことができると指摘しています。ただし、SetはJavascriptの比較的新しいアフォーダンスであり、ES6以前の環境では機能しないことに注意してください。

Answer 2

あなたはへの呼び出しがあります：あなたのforループの内部

permutations.push(newArray.join('')); 

を。それはそこにはないはずです。もちろん、文字が重複している文字列を並べ替えると、うまく表示されません。たとえば、文字列 "aa"を並べ替えると、このアルゴリズム "aa"と "aa"の2つのエントリが得られます。ヒープのアルゴリズムはダプルを削除しようとしません、それは文字列内の各要素を一意であるとみなします。明らかに、あなたが気にしていることがあれば、それを削除することは自明です。