为何自定义myshuffle洗牌实现不正确？从概率角度解析

你提到的这个错误洗牌实现，核心问题在于每次循环都允许交换已经处理过的位置，导致不同初始位置的元素被交换的机会不均等，最终使得元素从位置i移动到j的概率p[i][j]无法保持均匀的1/n（n为数组长度）。咱们结合你的测试结果和数学推导来拆解：

先明确正确的Fisher-Yates洗牌逻辑 #

正确的Fisher-Yates洗牌是从后往前遍历，每次从未处理的元素中随机选一个和当前位置交换：

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

它的核心是只交换未处理的位置，每个元素只会被交换一次（最多），因此每个元素出现在任意位置的概率严格为1/n——因为每一步都是从剩余未选中的元素里公平选择，最终所有排列的概率相等。

错误实现的问题拆解 #

你的错误实现代码：

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]的角度分析 #

我们以你测试的n=5为例，看不同初始位置的元素概率分布：

1. 初始位置0的元素（你的测试中的'a'）
   第一次循环就会被随机交换到任意位置（概率各1/5），之后的4次循环中，每次都可能被再次交换。因为初始被完全打散，后续的交换相当于对均匀分布的再随机化，最终概率趋近于均匀的0.2，这和你的测试结果一致。

2. 初始位置i>0的元素（比如你的测试中的'b'、'c'、'd'、'e'）
   以初始位置4的'e'为例：

   • 在idx=0~3的循环中，只有当t_idx=4时，它才会被交换到idx位置，每次交换的概率仅为1/5，大部分时间它会留在位置4；
   • 直到idx=4的循环，它才会被随机交换到任意位置，但此时它的初始分布已经不均（大部分时间在位置4），后续的单次交换无法完全抹平这种不均。
     最终导致它在位置0的概率仅为0.164，位置3的概率高达0.242，位置4的概率维持0.2——这就是你测试结果中看到的分布差异。

本质原因：排列数与交换序列数不匹配 #

该错误实现的所有可能交换序列有n^n种（每次选t_idx有n种选择，共n次循环），而数组的全排列只有n!种。当n>2时，n^n无法被n!整除，因此不可能让每个排列的概率相等，必然导致某些排列的概率偏高，某些偏低，反映到p[i][j]上就是分布不均。

比如n=2时，2^2=4种交换序列，而全排列只有2种，其中一种排列会出现3次，另一种仅1次，概率完全不均。

总结 #

这个错误洗牌实现的核心问题是允许重复交换已处理位置，导致元素的交换机会不均等，最终p[i][j]无法保持均匀的1/n。正确的Fisher-Yates洗牌通过限制交换范围到未处理元素，保证了每个位置的概率公平。

内容的提问来源于stack exchange，提问作者xybaby