Knuth Shuffle - Githubissues

Knuth Suffle

知乎原文：https://zhuanlan.zhihu.com/p/73147939

设计一个公平的洗牌算法，或者说是，随机打乱一个数组。应该如何实现？

首先想到的是，随机选取数组中的两个元素并交换，随机k次。但是，k应该取多少？这样的做法是否公平？

在解决这个问题之前，我们要理解公平到底是指什么。随机打乱一个数组，就是把这个数组重新排列。重新排列一个数组一共会有n!个结果，如果我们能够等概率地给出这n!个结果中的任意一个，那么这个洗牌算法就是公平的。

但是，如果我们真的穷举出这n!种可能性，随着n的增大，计算时间的增长会比指数爆炸还要可怕。因此，我们换一种思路。公平还可以指：

每一个元素都能等概率地出现在每一个位置。或者反过来，每一个位置都能等概率地放置每个元素。

这个方法和上面穷举并选出其中一种的方法是等价的。

那么该如何实现呢？Knuth-Shuffle 算法只用了几行代码就可以实现：

from random import randrange

def knuth_shuffle(x):
    for i in range(len(x)-1, 0, -1):
        j = randrange(i + 1)
        x[i], x[j] = x[j], x[i]

x = list(range(10))
knuth_shuffle(x)
print("shuffled:", x)

伪代码如下：

for i from last downto 1 do:
    let j = random integer in range 0 <= j <= i;
    swap items[i] with items[j];

那么这个简单的算法是如何保证每个元素能够等概率地出现在每个位置呢？https://zhuanlan.zhihu.com/p/73147939中给出了详细的图文讲解，此处就不再赘述。

TiantongWang / MyBlogs

Knuth Shuffle #3

Knuth Suffle