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 慢)。