为什么我的shuffle实现不正确？

Question

当我想要改变一个序列时，我使用random.shuffle。我已经阅读了random.shuffle的源代码，它是Fisher–Yates_shuffle的典型实现。

但是，我曾经看到过一个混乱算法的错误实现。代码如下：

def myshuffle(lst):
    length = len(lst)
    for idx in xrange(length):
        t_idx = random.randint(0, length-1)
        lst[idx], lst[t_idx] = lst[t_idx], lst[idx]

我知道有问题，我已经测试过了。但我不清楚为什么这是不正确的。让我们说p[i][j]意味着元素从pos i移动到pos j的概率，有人能说清楚吗？

这是我的测试代码。

if __name__ == '__main__':
    random.seed()

    pre_lst = ['a', 'b', 'c', 'd', 'e']
    count = dict((e, {}) for e in pre_lst)
    TRY = 1000000

    for i in xrange(TRY):
        lst = pre_lst[:]
        myshuffle(lst)
        for alpha in pre_lst:
            idx = lst.index(alpha)
            count[alpha][idx] = count[alpha].get(idx, 0) + 1

    for alpha, alpha_count in sorted(count.iteritems(), key=lambda e: e[0]):
        result_lst = []
        for k, v in sorted(alpha_count.iteritems(), key=lambda e: e[0]):
            result_lst.append(round(v * 1.0 / TRY, 3))
        print alpha, result_lst

结果如下：

> a [0.2, 0.2, 0.2, 0.2, 0.2] 
> b [0.242, 0.18, 0.185, 0.192, 0.2] 
> c [0.21, 0.23, 0.173, 0.186, 0.2] 
> d [0.184, 0.205, 0.231, 0.18, 0.2]
> e [0.164, 0.184, 0.21, 0.242, 0.2]

Answer 1

数学：

这个算法不可能产生同样可能的结果：这个算法有n^n不同的方式通过循环（n迭代随机选择一个n索引），每个同样可能通过循环产生n!可能的排列之一。但n^n几乎永远不会被n!整除。因此，该算法不能产生均匀分布。

将其与Fisher-Yates进行比较，在每次n迭代中，交换索引池减少1。在这里，正好有穿过树的n!路径，每个路径恰好产生一个n!可能的排列。

对于短名单（n <= 4），你可以用铅笔和纸画两棵树。

经验：

您可以编写一个函数，通过shuffle树生成所有l**l可能的路径，然后计算结果：

def shuffle_combos(lst, i=0):
  l = len(lst)
  for j in range(l):
    lst_ = lst[:]
    lst_[i], lst_[j] = lst_[j], lst_[i]
    if i == l-1:
      yield tuple(lst_)
    else:
      for perm in shuffle_combos(lst_, i=i+1):
        yield perm

>>> from pprint import pprint
>>> from collections import Counter
>>> pprint(list(Counter(shuffle_combos([1,2,3])).items()))
[((1, 3, 2), 5),
 ((3, 2, 1), 4),
 ((2, 3, 1), 5),
 ((1, 2, 3), 4),
 ((2, 1, 3), 5),
 ((3, 1, 2), 4)]
#            ^- 3^3 = 27 paths, but 3! = 6 permutations
#            but 27 % 6 != 0
>>> pprint(list(Counter(shuffle_combos([1,2,3,4])).items()))
[((4, 1, 2, 3), 8),
 ((1, 3, 2, 4), 10),
 ((3, 4, 1, 2), 11),
 ((1, 2, 4, 3), 10),
 ((1, 2, 3, 4), 10),
 ((1, 3, 4, 2), 14),
 ((1, 4, 2, 3), 11),
 ((4, 2, 1, 3), 9),
 ((2, 4, 3, 1), 11),
 ((2, 1, 3, 4), 10),
 ((4, 2, 3, 1), 8),
 ((3, 1, 2, 4), 11),
 ((4, 3, 1, 2), 10),
 ((2, 4, 1, 3), 11),
 ((2, 3, 1, 4), 14),
 ((3, 1, 4, 2), 11),
 ((3, 4, 2, 1), 10),
 ((1, 4, 3, 2), 9),
 ((3, 2, 4, 1), 11),
 ((2, 3, 4, 1), 14),
 ((4, 1, 3, 2), 9),
 ((4, 3, 2, 1), 10),
 ((3, 2, 1, 4), 9),
 ((2, 1, 4, 3), 15)]

而且你可以看到它们分布不均匀。