Warum gibt mein Permutationsalgorithmus für alle Permutationen dasselbe Ergebnis?

Question

Dies ist das erste Mal, dass ich selbst eine Frage zu SO stellen muss. Ich finde immer Antworten, um die meisten meiner Probleme zu lösen, aber dieses Mal bin ich mit dem Permutationsalgorithmus eines Heaps beschäftigt. Ich habe versucht, diese Herausforderung für eine Weile ohne Erfolg zu lösen, also komme ich zu euch, die ein besseres Programmierwissen haben als ich.

Ich schrieb etwas Javascript-Code, um jede mögliche Permutation eines Wertes rekursiv zu finden: entweder ein Array oder eine Zeichenkette. Mein Code scheint perfekt zu funktionieren, wenn ich die permutierten Werte console.log(), aber wenn ich sie in ein anderes Array verschiebe, bekomme ich den gleichen Wert für alle von ihnen. Ich bin verwirrt. Vielleicht mache ich etwas Dummes, wer weiß. Jede Hilfe würde geschätzt werden, danke in fortgeschrittenen Kerlen.

Mein Code enthält zwei separate Funktionen: die eine wechselt die Elemente und die andere rekursiv die mögliche Permutation.

arr = ["a", "b", "c"]; 
newArr = []; 

// swap mechanism here 
function swap(arr, pos1, pos2) { 
    var temp = arr[pos1]; 
    arr[pos1] = arr[pos2]; 
    arr[pos2] = temp; 
}; 

function perm(arr, nArr, n) { 
    n = n || arr.length; 
    if (n === 1) { 
     console.log(arr); // console.log() works great 
     newArr.push(arr); // pushing the permuted values does not 
    } 
    else { 
     for(var i = 1; i <= n; i += 1) { 
      perm(arr, nArr, n - 1); 
      if (n % 2) { 
       var j = 1; 
      } 
      else { 
       var j = i; 
      } 
      swap(arr, j - 1, n - 1); 
     } 
    } 
}; 

Answer 1

Dies ist einfach (Heap) Referenz vs. (Stapel) Wert Frage. Der Grund ist ziemlich einfach: arr in allen rekursiven Aufrufen verweist auf das gleiche Array im Speicher. Wenn Sie also newArr.push(arr) aufrufen, wird ein weiterer Verweis auf das gleiche Objekt zur Ergebnisliste hinzugefügt. Und wenn Sie swap tun, tauschen Sie Elemente für alle Elemente von newArr, da sie auf das gleiche Array zeigen. Siehe auch Copying array by value in JavaScript für eine mögliche Problemumgehung. (Verwenden Sie grundsätzlich die Methode Array.slice, um eine unabhängige Kopie zu erstellen).