对Fisher Yates Shuffle的错误实施有偏见

问题描述 投票:1回答:1

我实现了改组算法:

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

附:我对数学不太满意。

python algorithm combinatorics
1个回答
0
投票

这不是任何方式的证据,但您可以通过运行偏差算法一百万次快速提出放置概率的分布。它看起来像维基百科的这张照片:

permute with all order bias

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

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

编辑:我运行了一些模拟,这个结果很可能是错误的。我会留下这个答案,直到我能想出更好的东西。

© www.soinside.com 2019 - 2024. All rights reserved.