为什么我的排列算法给了我所有排列相同的结果？

这是我第一次在SO上自问一个问题。我总是找到答案来解决我的大部分问题，但是这次我遇到了一些堆的排列算法。我一直试图解决这个挑战一段时间没有成功，所以我来找你们比我有更好的编程知识。为什么我的排列算法给了我所有排列相同的结果？

我写了一些Javascript代码来递归地查找每个可能的值排列：一个数组或一个字符串。我的代码似乎完美工作，当我console.log（）排列的值，但是当我把他们推到另一个数组时，我得到了所有他们相同的值。我很困惑。也许我在做一些愚蠢的事，谁知道。任何帮助将不胜感激，感谢先进的家伙。

我的代码包含两个独立的函数：一个是交换元素，另一个是递归地找到可能的排列。

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); 
     } 
    } 
};

来源

2017-08-10 Wadson Fourrien

欢迎来到StackOverflow。请阅读并遵守帮助文档中的发布准则。 [最小，完整，可验证的示例]（http://stackoverflow.com/help/mcve）适用于此处。在发布您的MCVE代码并准确描述问题之前，我们无法为您提供有效的帮助。我们应该能够将发布的代码粘贴到文本文件中，并重现您描述的问题。 – Prune

这是简单（堆）引用与（堆栈）值问题。原因很简单：所有递归调用中的arr引用内存中的相同数组。因此，当您致电newArr.push(arr)时，将另一个对同一对象的引用添加到结果列表中。当你做swap时，你交换newArr所有元素的元素，因为它们指向相同的数组。有关可能的解决方法，另请参阅Copying array by value in JavaScript。（基本上使用Array.slice方法创建一个独立的副本）。

来源

2017-08-10 21:26:47 SergGr

非常感谢你，兄弟。我很困惑，但我想我明白这个问题是什么。一个简单的问题：console.log（）如何显示所有置换值？我不太了解那部分。 –

@WadsonFourrien，'console.log'显示执行时的当前值。那时（只）数组处于你想要的状态（并且来自'newArr'的所有引用指向那个状态中的同一个数组）。但是当你下次修改那个（相同的）数组时，你调用'swap'，它的状态现在与你上次记录的不同。在第3次或第4次迭代中设置一个断点并查看'newArr'可能会有所帮助，以了解它如何包含对同一内存的多个引用。 – SergGr

最后，解决这个问题。再次感谢你的帮助：） –

为什么我的排列算法给了我所有排列相同的结果？

回答

相关问题