错误实施Fisher Yates Shuffle的顺序偏向 [英] Order bias in wrong implementation of Fisher Yates Shuffle

问题描述

我将改组算法实现为：

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中哪个排列的发生概率最高，哪个排列的发生概率最低！ 排列。如果是，那么那个排列是什么？

As this algorithm is biased. I just wanted to know for any n(n ≤ 17), is it possible to find that which permutation have the highest probablity of occuring and which permutation have least probablity out of all possible n! permutations. If yes then what is that permutation??

例如 n = 3 ：

a = [1,2,3]

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

There are 3^3 = 27 possible shuffle

否。发生不同排列：

1 2 3 = 4

3 1 2 = 4

3 2 1 = 4

1 3 2 = 5

2 1 3 = 5

2 3 1 = 5

PS我数学不太好。

P.S. I am not so good with maths.

推荐答案

这绝不是证明，但您可以通过运行有偏差的对象来快速得出展示位置概率的分布算法一百万次。看起来像来自维基百科的图片：

This is not a proof by any means, but you can quickly come up with the distribution of placement probabilities by running the biased algorithm a million times. It will look like this picture from wikipedia:

无偏分布在每个字段中占14.3％。

An unbiased distribution would have 14.3% in every field.

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

To get the most likely distribution, I think it's safe to just pick the highest percentage for each index. This means it's most likely that the entire array is moved down by one and the first element will become the last.

编辑：我进行了一些模拟，结果很可能错误。在我提出更好的答案之前，我会一直保留这个答案。

I ran some simulations and this result is most likely wrong. I'll leave this answer up until I can come up with something better.

这篇关于错误实施Fisher Yates Shuffle的顺序偏向的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！