JavaScript字符串中的加擾字符，是否可能具有相同的可能性？

我目前正在研究一個簡單的函數，它將對輸入的字符串進行編碼，其中所有可能的排列組合都是可能的。我的代碼如下。JavaScript字符串中的加擾字符，是否可能具有相同的可能性？

function scramble(s) { 
    result = s.split(""); 
    for(var i = 0; i < s.length; i++) { 
     var j = Math.floor(Math.random() * (i + 1)); 
     var scrambler = result[i]; 
     result[i] = result[j]; 
     result[j] = scrambler; 
    } 
    return result.join(""); 
}

到目前爲止，代碼似乎是工作的罰款...但是將所有可能的排列也同樣有可能？（我相信Math.random和Math.floor，但是當我在運行時期間觀察i和j時，我會感到奇怪的輸出。）

來源

2013-09-22 jadengore

你問我們要證明你的算法的正確性嗎？爲什麼不使用[Fisher-Yates]（http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle）等知名或研究的內容？ – Rup

檢查一下 - 第一個字符可能會在第一次迭代中出現在哪裏？ – Leeor

請參閱http://www.robweir.com/blog/2010/02/microsoft-random-browser-ballot.html –

除非我在這裏有一個可怕的錯誤（請檢查它是否合理），我相信這段代碼不會創建均勻分佈的排列。

檢查例如第一個字符會留在原地的機會 - 當我是0時，它不能被任何人取代，當我是1時，元素0和1將有50％的交換機會，等等。因此，總的來說，結果[0]將以概率保留在其位置1/2 * 2/3 * 3/4 ... n-1/n = 1/n

但是，最後一個元素的保留概率只是（n-1）/ n，因爲您只有一次機會交換它你可以從整個陣列中選擇。

如果您用s.length代替(i+1)，您可能會獲得更好的分配，但最好的辦法是採取已知的措施。你可以從這裏開始 - http://en.wikipedia.org/wiki/Random_permutation

來源

2013-09-23 00:15:08 Leeor

JavaScript字符串中的加擾字符，是否可能具有相同的可能性？

回答

相關問題