测试混洗代码

Question

我正在测试我编写的一些代码来随机排列数组的元素。虽然不是真正的 "professional test"，但我想知道结果。
我生成了一个随机数组并不断对其进行洗牌，直到对数组进行排序。我预计获得排序顺序的次数约为 n!/2，最大洗牌次数约为 n!，其中 n 是数组中元素的数量。

对于 5 个元素，洗牌次数平均为 108 次左右，对于 6 个元素为 615 次左右。我很惊讶地发现即使我只有 5 个元素，某些洗牌也需要超过 500 次。

我的问题是，这个结果是否有解释，and/or我对预期洗牌的推理是否正确？我的随机码

void shuffle(int* array, int length)
{
    int i=0;
    int r =0;
    for(i=0;i<length;i++)
    {
        r = randomInRange(0,i);
        swap(array,i,r);
    }
}

Answer 1

为什么是 n!/2？排列数为n!，所以在n!之后洗牌你只希望正确排序一次数字。洗牌次数没有上限——如果有 5 张牌，你有 119/120 的机会在每次迭代中得到无序结果，而且这可能会持续很长时间。

这是我编写的 Python 脚本的输出，用于计算正确猜测从 1 到 120 的随机数所需的次数：

[17, 43, 251, 72, 4, 10, 41, 61, 74, 22, 172, 49, 43, 66, 994, 99, 59, 88, 255, 48]

平均值为 123.4，这与预期的差不多，但即使在这个小样本集中，单个值也介于 4 到 994 之间。

~~但是，对于您的情况，结果略有不同。这是因为您使用的改组算法会产生偏斜的结果。 (Jeff Atwood has written a useful blog post on the subject.)~~

~~我建议您改用 Fisher-Yates algorithm。~~

测试混洗代码

Test for shuffling code

c

shuffle