相关疑难解决方法(0)

着名的Fisher-Yates shuffle算法可用于随机置换长度为N的阵列A:

For k = 1 to N
    Pick a random integer j from k to N
    Swap A[k] and A[j]

我一遍又一遍地告诉我的一个常见错误是:

For k = 1 to N
    Pick a random integer j from 1 to N
    Swap A[k] and A[j]

也就是说,不是从k到N选择一个随机整数,而是从1到N中选择一个随机整数.

如果你犯了这个错误怎么办？我知道由此产生的排列不是均匀分布的,但我不知道对于最终的分布有什么保证.特别是,有没有人有关于元素最终位置的概率分布的表达式？

Collections.shuffle()经过一个Collection向后的每个索引,然后用随机索引交换它,包括或之前.我想知道为什么,所以我尝试做同样的事情,但交换任何随机索引Collection.

这是Collections.shuffle()代码的混乱部分:

for (int i=size; i>1; i--)
    swap(arr, i-1, rnd.nextInt(i));

这是我的算法:

Random r = new Random();
for (int i = 0; i < a.size(); i++) {
    int index = r.nextInt(a.size());
    int temp = a.get(i);
    a.set(i, a.get(index));
    a.set(index, temp);
}

我发现Collections.shuffle()当我同时运行两ArrayList百万次时,我的代码分布比我的代码更均匀.此外,在运行我的代码时:

[0,1,2,3,4]

似乎以下排列最常出现:

[
1,0,3,4,2]
[1,2,3,4,0]
[1,2,0,4,3 ] [0,2,3,4,1]
[1,2,3 ] ,0,4]

有人可以解释一下原因吗？