什么是洗牌最好的算法？

-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

什么是洗牌最好的算法？

回答

相关问题