混洗算法之間的區別

Question

假設我們要編寫一個方法來生成混洗牌。現在讓它變得非常簡單，無視西裝，所以我們有52張牌。

一種算法將是：

• 52個填充元件的陣列與1第一元件，2秒，等等。
• 編寫一個迭代X次的for循環，並在每次迭代期間選擇兩張隨機卡並交換它們。
• X越大，洗牌的隨機化程度越高。

另一種算法：

• 填充陣列像先前。
• 編寫一個迭代次數爲26的for循環，並在每次迭代過程中挑選兩個隨機數，並將這兩個數字放在另一個存儲新拾取數字的52個元素數組的前面。
• 在每次迭代中，從原始數組中刪除添加到新數組的兩張卡片。

我知道有更好的洗牌算法，但關於這兩個，哪一個更好，爲什麼？

Answer 1

第二種算法似乎是一個unrolled-通過兩個實施Fisher-Yates。這種洗牌具有以均勻分佈選擇所有可能結果之一的特性。大多數人會稱之爲「公平」或「完美」的洗牌。如果您的隨機數發生器提供的是無偏差的結果，則不需要重複額外的隨機性操作。

第一個算法可能漸近地逼近我不知道什麼樣的分佈類型。我會因各種原因避免它。主要是因爲我不知道在產生一個好的洗牌之前X需要多大，但我相信它超過了52。除了故意模擬不適當的洗牌之外，我無法想到這種算法的良好應用。

第一種算法正在運行，這在某些情況下是有益的，但是如果需要，那麼您可以修改第二種算法以類似的方式運行。

Answer 2

更好的一個是：

1. 產生一些臨時陣列
2. 訂單在C＃中使用臨時數組作爲關鍵

卡的陣列，它看起來

Random r = new Random(DateTime.Now.Miliseconds); 
string [] cards = new string[52]{"1","2",.....}; 
int [] temp = new int[52]; 
for(int i=0;i<52;i++) 
{ 
    temp[i]=r.Next(); 
} 

Array.Sort(temp,cards); 

Answer 3

52號

你必須定義「更好」的含義。第一種算法的問題是有些元素可能永遠不會改變位置。例如，如果你永遠不會隨機得到低數字，那麼第一張卡片將是有序的。

第二種算法會讓你更隨機化。但是，如果你只運行一次，那麼物品在最終的地方是可以預測的。

我要麼運行算法2分多次，或洗牌就像你做一個真正的甲板

1: Split the deck into two arrays of 26 
2: Take the top card from one of the arrays at random and put it into a new array of size 52 
3: Keep doing this until one array is empty, put the remaining cards of the other array into the size 52 array 
4: Repeat 

這將淨賺你一個很好的隨機

Answer 4

第一種算法會產生高偏置分佈，因爲它很可能會在初始位置留下一些卡，容易出現「雙交換」問題（交換兩張相同的卡，導致初始卡狀態）。

第二算法，as @sh1 mentioned是Fisher-Yates algorithm展開的版本，其中一個小的例外：它沒有更多的直鏈的，如從列表中刪除項本身是線性操作，它是在每個迭代執行，從而整體算法複雜度爲O（ N^2）。

的Fisher-Yates algorithm高效的版本將是以下幾點：

僞代碼（因爲你沒有提到所選擇的語言）

for i from n − 1 downto 1 do 
    j ← random integer with 0 ≤ j ≤ i 
    exchange a[j] and a[i] 

和Python實現，以防萬一:)

import random 
n = 52 
arr = [i for i in range(1,n+1)] 

for i in range(n-1, 1, -1): 
    elem_to_swap = random.randint(0, i) 
    arr[elem_to_swap], arr[i] = arr[i], arr[elem_to_swap]