Fisher–Yates Shuffle 算法

这里我们讨论， Fisher–Yates shuffle， 也叫 Knuth shuffle。 Knuth在其著作中提出， 不过后来credit给了 Fisher-Yates。 其主要的思想是利用一个均匀分布的Random源来帮助选择，最后确保长为N的列表中每一个元素被选中的概率1/N。 这里简要描述一下，把N个数想成N张牌，从小到大在手上排好，每次随机一个1到当前牌数的数字，然后把这一张抽出来，放在桌子上，不断重复这个步骤知道手中的牌全部摆在了桌子上，这个桌子上的排列就是一个随机排列。

1def old_shuffle(n):
2    res = []
3    candidates = [_ for _ in range(1,n+1)]  # 1, ..., n
4    for i in range(n,0,-1):  # n, ..., 1
5        k = random.randint(1,i)
6        res.append(candidates[k-1])
7        candidates = candidates[:k-1] + candidates[k:]
8    return res

这个算法和目前流行的shuffle算法有一些不一样。 目前的是 Durstenfeld 提出的改进的 Fisher–Yates shuffle。 这里主要是在上面第七行， 相当于每次放下一张牌，就需要去整理一下剩下的牌。 实际上这个复杂度是 O(n^2). 改进的算法是 O(n) 的时间复杂度, 而且是一个 in-place 的算法。不用每次生成array的copy，尤其是当这个数组很大的时候， 如果要每次generate一个新的数组成本很大。

1def modern_shuffle(n):
2    res = [_ for _ in range(1,n+1)]  # 1, ..., n
3    for i in range(n-1,0,-1):  # n-1, ..., 1
4        k = random.randint(0, i)
5        res[k], res[i] = res[i], res[k]
6    return res

这一过程的形象理解是一个扑克玩家在整理手中的牌，从后向前，每次随机的把当前牌和之前的牌交换。

概率论解释

接下来我们来用概率论来解释一下为何每一个牌出现在当前位置的概率都是1/N. 这里最好用的是归纳法。

  1. 我们先看 base cases。 当前有N张牌， 我们随机找到一张牌，和最后一张牌交换，每一张牌出现这里的概率是 1/N 无疑。

  2. 那么下一步， 在N-1的位置(N-2 if 0-based index)， 有1/(N-1)的概率从当前剩余的牌中抽到任意一张。 那么我们来计算事件 E: 任意一张牌在这个位置出现的概率 P(E)。如果一张牌要在这里出现， 那么也就是说第一轮不能被抽中， 否则 不会在这里出现,

$$ P(E) = (1-\frac{1}{N} )\times \frac{1}{N-1} = \frac{1}{N} $$

  1. 以此类推， 在接下来的位置， 概率都是 1/N.

Inside-out

Wikipedia上还有一个shuffle算法的实现， 叫做 inside-out

1def inside_out_shuffle(source):
2    n = len(source)
3    res = [0]*n
4    for i in range(n):
5        k = random.randint(0,i)
6        if k!=i:
7           	res[i] = res[k]
8        res[k] = source[i]
9    return res

这个算法的概率结果也可以用归纳法。

  1. i=0 的时候 source 0百分之一百出现在这一个位置
  2. i=1的时候, source 0和1 以1/2的概率出现在这两个位置
  3. 以此类推， 当i=N-1的时候， 任意source都以1/N的概率出现任意位置

这个算法还有一个优势就是， 他虽然不是inplace但是可以是on-the-fly的， 也就是说我们可以不用知道n就可以做shuffle。这个过程可以理解为取牌的过程， 你并不知道最终你的手上会有多少张，但是你想确保无论何时这都是一个随机排列。这样以为这个算法是流计算算法。

代码示意如下：

1a=[]
2while source.peek >0:
3    k = random.randint(0, len(a))
4    if k==len(a):
5        a.append(source.next)
6    else:
7        a.append(a[k])
8        a[k] = source.next

References

  • {% post_link leetcode/382-linked-list-random-node %}
  • {% post_link leetcode/384-shuffle-an-array %}
  • {% post_link leetcode/398-random-pick-index %}