什麼是洗牌最好的算法？

-2

鑑於N卡的有限集合，什麼是洗牌最好的方法（算法），所以我會用最少的步驟獲得最好的洗牌卡片組以獲得最大的隨機排列？什麼是洗牌最好的算法？

什麼是最小步驟的最佳解決方案？

來源

2016-10-15 Tal Avissar

你怎麼定義最好的洗牌包？ – Pang

定義「最佳」。此外，這個問題主要是基於意見的，或者要求提供第三方內容的建議，這兩者在Stack Overflow上都是無關緊要的。 –

最小步驟和卡片之間的距離，顯然某些類型的洗牌優於其他類型。 –

這是典型的（我認爲可證明是最好的，使用需要LEN（x）的階乘排列位的確切數目）：

def shuffle(x): 
    """Shuffle list x in place, and return None.""" 
    for i in reversed(range(1, len(x))): 
     # pick an element in x[:i+1] with which to exchange x[i] 
     j = int(random() * (i+1)) 
     x[i], x[j] = x[j], x[i]

來源

2016-10-15 10:23:55

看起來不錯。重要的一點是，你可能首先想到的是，將i上的隨機數交換爲N，而不是0到N。在0到N之間交換給出了一個奇怪的，不均勻的分佈。 –

使用Fisher Yates algorithm。許多編程語言使用該算法的變體來混洗有限集合的元素。這是Fisher Yates算法的僞碼（由Richard Durstenfeld優化的版本）：

-- To shuffle an array a of n elements (indices 0..N-1): 
for i from N−1 downto 1 do 
    j ← random integer such that 0 ≤ j ≤ i 
    exchange a[j] and a[i]

該算法確保均勻分佈。對於N卡，有N！可能的混洗組合。這裏排列的N!中的任何一個都可能返回。時間複雜度是O(N)。

來源

2016-10-15 13:47:26

什麼是洗牌最好的算法？

回答

相關問題