python - Fisher Yates Shuffle 错误实现中的顺序偏差

Question

我将洗牌算法实现为:

import random
a = range(1, n+1) #a containing element from 1 to n
for i in range(n):
    j = random.randint(0, n-1)
    a[i], a[j] = a[j], a[i]

因为这个算法是有偏见的。我只是想知道对于任何 n(n ≤ 17)，是否有可能在所有可能的 n! 排列。如果是，那么该排列是什么？

例如n=3:

a = [1,2,3]

有 3^3 = 27 种可能的洗牌

没有。不同排列的出现:

1 2 3 = 4

3 1 2 = 4

3 2 1 = 4

1 3 2 = 5

2 1 3 = 5

2 3 1 = 5

附言我数学不太好。

Answer 1

这无论如何都不是证明，但您可以通过运行有偏差的算法一百万次来快速得出放置概率的分布。它看起来像来自维基百科的这张图片:

无偏分布在每个领域都有 14.3%。

为了获得最有可能的分布，我认为为每个索引选择最高百分比是安全的。这意味着很可能整个数组向下移动一个，第一个元素将成为最后一个。

编辑:我进行了一些模拟，这个结果很可能是错误的。在我想出更好的办法之前，我会留下这个答案。