python - 这种洗牌算法是否以均匀的概率产生每个排列？

Question

我已经看到了一个特定的朴素洗牌算法是如何有偏见的，我觉得我基本上明白了这一点，并且我明白了 Fischer-Yates 算法如何没有偏见。我有以下算法，这是我在考虑如何洗牌列表时首先想到的算法。我知道它消耗两倍的内存并且运行时间不必要地长，但我仍然很好奇它是否产生具有均匀分布的每个排列，或者是否有一些我没有看到的隐秘原因导致它有偏差。

我还想知道随机洗牌是否还有其他一些“不需要的”属性，例如列表中各个位置填充某些值的概率是相关的。

def shuf(x):
    out = [None for i in range(len(x))]
    for i in x:
        pos = rand.randint(0,len(x)-1)
        while out[pos] != None:
            pos = rand.randint(0,len(x)-1)
        out[pos] = i
    return out

我在 20 个元素的列表上生成了该热图，运行了 10^6 次试验，并生成了以下结果。映射的 (i,j) 坐标表示列表的第 i 个位置被原始列表的第 j 个元素填充的概率。

虽然我没有看到热图的任何模式，但看起来方差可能很大。或者这可能是热图夸大了方差，因为，嘿，最小值和最大值必须出现在某个地方。

Answer 1

不良属性 - 如果您要洗牌一大组，这可能会很昂贵:

 while out[pos] != None:
            pos = rand.randint(0,len(x)-1)

想象一下 len(x) == 100,000,000 并且您已经放置了 90,000,000 - 在获得命中之前您将循环很多次。

有趣的练习:

1. 在 10e6 次迭代中简单生成 1 到 len(x) 之间的随机数的热图是什么样子？

2. 作为比较，Fischer-Yates 的热图是什么样的？

乍一看，在我看来，给定一个统一的 RNG，它应该产生真正的随机分布(尽管比 Fischer-Yates 慢)。