python - 为什么我的随机播放实现不正确？

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]表示元素从位置i移动到位置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 )，您可以用铅笔和纸画出两棵树。

根据经验:

您可以编写一个函数来生成所有 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)]

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