爲什麼我的排列算法給了我所有排列相同的結果？

這是我第一次在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

最後，解決這個問題。再次感謝你的幫助：） –

爲什麼我的排列算法給了我所有排列相同的結果？

回答

相關問題