Pourquoi mon algorithme de permutation me donne-t-il le même résultat pour toutes les permutations?

Question

C'est la première fois que je dois poser une question moi-même sur SO. Je trouve toujours des réponses pour résoudre la plupart de mes problèmes mais cette fois je suis coincé avec un algorithme de permutation de tas. J'ai essayé de résoudre ce problème pendant un certain temps sans succès, donc je viens à vous les gars qui ont une meilleure connaissance de la programmation que moi.

J'ai écrit du code Javascript pour trouver récursivement toutes les permutations possibles d'une valeur: soit un tableau, soit une chaîne. Mon code semble fonctionner parfaitement quand je console.log() les valeurs permutées mais quand je les pousse à un autre tableau j'obtiens la même valeur pour chacun d'eux. Je suis confus. Peut-être que je fais quelque chose de stupide, qui sait. Toute aide serait appréciée, merci aux gars avancés.

Mon code contient deux fonctions distinctes: l'une permet l'échange des éléments et l'autre trouve de façon récursive la permutation possible.

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

Il s'agit d'une référence simple (tas) par rapport à la question (pile). La raison est assez simple: arr dans tous les appels récursifs fait référence au même tableau en mémoire. Ainsi, lorsque vous appelez newArr.push(arr), une autre référence au même objet est ajoutée à la liste des résultats. Et lorsque vous faites swap, vous échangez des éléments pour tous les éléments de newArr car ils pointent vers le même tableau. Voir également Copying array by value in JavaScript pour une solution de contournement possible. (Utilisez essentiellement la méthode Array.slice pour créer une copie indépendante).