扑克洗牌的算法比较

洗牌
计算机科学二级

Alice和Bob想为他们的扑克俱乐部制作一台洗牌机。问题是，他们提出了不同的算法，因此无法决定应用哪一种算法：

爱丽丝的算法思路：从左到右依次，每张牌只和位于右边的任何牌交换位置。
鲍勃的算法思路：从左到右一次，每张牌与任何其他牌交换位置。
谁的算法更好，或者这真的很重要吗？

运用可视化直观地看到两种思路的算法比较：

brilliant_card_shuffleFigure_1.png

答案可能一开始是反直觉的。为什么Bob的算法不好？难道它不能生成所有的排列组合吗？答案是肯定的，它可以生成所有的排列组合，但不是均匀的。总共有多达 n^n = n的n次方移动方式，但问题在于，n副牌的排列也只有n！个排列组合的方式。

由于n^n不能整除n！，意味在一般情况下，并不是所有的排列组合都有同等的机会产生。

现在我们确信鲍勃的算法是坏的，但它有多坏呢？注意到了，如果一张牌被换到左边，它就不能再往左走了!

还不服气吗? 让数据来说话。

上图左边是Alice的算法，右图是Bob的算法。
x轴是数字，y轴是它经过算法后最终的位置。越亮的单元格，数字最终出现在那个位置的频率越高。正如你所看到的，大部分的数字最后都在它的左边!

如果你对可视化是如何生成的感兴趣，这里是代码。

from random import randint
import matplotlib.pyplot as plt

n = 1000 #模拟1000次洗牌
x_data = []
y_data = []
# start simultion for distributed permutations
for simulation in range(n):
    # perfectly sorted array
    arr = [x + 1 for x in range(n)]
    for i in range(n):
        r = randint(0, i) # correct way

        # swap two elements
        arr[r], arr[i] = arr[i], arr[r]

    # collect result
    for i in range(n):
        x_data.append(arr[i])
        y_data.append(i+1)
# end simulation

# plot
fig, axs = plt.subplots(ncols = 2, sharey=True, figsize=(14, 6))
fig.subplots_adjust(hspace=0.5, left=0.07, right=0.93)
hb = axs[0].hexbin(x_data, y_data, gridsize=50, cmap='inferno')
axs[0].axis([0, 1000, 0, 1000])
axs[0].set_title("Distributed Permutation")
cb = fig.colorbar(hb, ax=axs[0])
cb.set_label('frequency')

x_data = []
y_data = []
# start simultion for biased permutations
for simulation in range(n):
    # perfectly sorted array
    arr = [x + 1 for x in range(n)]
    for i in range(n):
        r = randint(0,n-1) # wrong way

        # swap two elements
        arr[r], arr[i] = arr[i], arr[r]

    # collect result
    for i in range(n):
        x_data.append(arr[i])
        y_data.append(i+1)
# end simulation

# plot
fig.subplots_adjust(hspace=0.5, left=0.07, right=0.93)
hb = axs[1].hexbin(x_data, y_data, gridsize=50, cmap='inferno')
axs[1].axis([0, 1000, 0, 1000])
axs[1].set_title("Biased Permutation")
cb = fig.colorbar(hb, ax=axs[1])
cb.set_label('frequency')

plt.show()