洗牌
计算机科学二级
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()
网友评论