堆的算法排列JavaScript和遞歸堆棧？

我有一個任務來計算基於堆的算法排列重複的字符串。我想要做的第一件事是輸出交換的字符串，我發現這個代碼jake's answer有人可以幫助我理解這個代碼循環內的遞歸嗎？這個函數的輸出是交換字符串。堆的算法排列JavaScript和遞歸堆棧？

function permAlone(string) { 

var arr = string.split(''), // Turns the input string into a letter array. 
      permutations = []; // results 

function swap(a, b) { 
debugger; // This function will simply swap positions a and b inside the input array. 
var tmp = arr[a]; 
arr[a] = arr[b]; 
arr[b] = tmp; 
} 

function gen(n) { 
    debugger; 
    if (n === 1) { 
    var x =arr.join(''); 
    permutations.push(x); 
    } else { 
    for (var i = 0; i != n; i++) { // how does this loop executes within the call stack? 
    gen(n - 1); 
    debugger; 
    swap(n % 2 ? 0 : i, n - 1); // i don't understand this part. i understand the swap function, but I don't get how indexes are swapped here 
    } 
} 
} 
gen(arr.length); 
return permutations; 
} 
permAlone('xyz'); // output -> ["xyz","yxz","zxy","xzy","yzx","zyx"]

我一直在調試器上試驗它，但仍然無法得到所發生的事情。

來源

2016-09-09 learningjavascriptks

請正確地在功能中縮進代碼。閱讀縮進代碼要容易得多。我自己試着編輯你的代碼，但是它不會將空格轉換爲編輯的最小6個字符。 –

我不知道你是什麼意思由

理解這段代碼中遞歸在循環

如果你的意思是你想看到在一個循環的形式算法，而不是一個遞歸版本，您可以在wikipedia page here中以僞代碼方式並排查看它們。

對於代碼中你的問題：

請問這個循環調用堆棧中執行？

你是正確的參考調用堆棧，這是一個關於遞歸的一般問題。如果你不明白遞歸如何處理堆棧，你可以參考this really nice and simple video，它演示了在java中使用階乘計算的遞歸調用（在4:00左右開始）。

您所看到的這一行與遞歸函數中的其他行沒有區別。我們首先定義i併爲其賦值0。我們繼續檢查它是否滿足for循環的條件。如果是，我們進入循環並執行遞歸調用的循環內的第一行。在遞歸調用中，我們有一個新的堆棧框架，它不知道我們在執行遞歸調用之前定義的i變量，因爲它是一個局部變量。所以當我們到達新的調用中的循環時，我們定義了一個新的變量i，首先將它賦值爲0，並在循環在這個堆棧幀/調用實例中重複時遞增。當這個調用完成時，我們刪除堆棧幀，並恢復到先前的棧幀（我們開始的那個），其中i = 0仍然存在，我們繼續到下一行。所有的調用都可以訪問arr和permutations變量，因爲函數被定義在變量的同一範圍內（在函數permAlone內），所以在每個調用中 - 無論我們所處的棧幀如何，對這些變量是針對相同的實例製作的。這就是爲什麼對排列進行的每次推動都會增加現有結果，並在函數結束時返回變量時出現在結果中。

我不明白這個部分。我瞭解交換功能，但我沒有得到如何在這裏交換索引

索引在這裏沒有交換。這只是一個調用具有正確索引的交換函數。

swap(n % 2 ? 0 : i, n - 1);

只是

swap(a, b);

與

a = n% 2 ? 0 : i; 
b = n - 1;

如果a的部分是什麼迷惑你，那麼這是一種利用the ternary operator for conditional value。也就是說，它是符號，用於形成根據具體情況進行不同評估的表達式。該用途是通過

<<i>boolean epression</i>> ? <<i>value-if-true</i>> : <<i>value-if-false</i>>

爲了評價上面，第一< 布爾表達式>進行評價。如果它的價值是true那麼整個表達式評估爲< 如果真值>。否則，整個表達式被評估爲< 如果值爲假>。

在代碼本身，a，n % 2是布爾表達式 - js的劃分n通過2並採取剩餘部分。其餘的是1或0。 js分別將其隱含轉換爲true和false。所以，如果n是奇數，我們得到

a = 0

，如果它連我們得到

a = i

的算法需要。

來源

2016-09-09 15:53:44

堆的算法排列JavaScript和遞歸堆棧？

回答

相關問題