洗牌代码测试

我正在测试一些我写入洗牌数组元素的代码。虽然不是真正的“专业测试”，但我对结果感到疑惑。
我生成了一个随机数组，并保持洗牌，直到数组排序。我预计获得排序顺序的次数约为n！/ 2，并且最大的随机播放需要在n！左右，其中n是阵列中元素的数量。洗牌代码测试

有5个元素，洗牌次数平均为108次左右，6次为615左右。我很惊讶地发现，即使我只有5个元素，某些洗牌花费了500次以上。

我的问题是，有没有这个结果的解释，和/或我的理由是预期洗牌是否正确？我的洗牌码

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); 
    } 
}

来源

2015-07-21 jogabonito

这就是着名的[bogosort]（https://en.wikipedia.org/wiki/Bogosort）。 – pmg

排序的顺序是n中的一个！可能的订单。如果混洗以相等的概率产生每个订单1/n！排序所需的洗牌次数具有[几何分布]（https://en.wikipedia.org/wiki/Geometric_distribution），其预期值为n !. – Joni

最坏的情况是无界的。性能也可能取决于随机数的分布。 – Daniele

为什么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。~~

来源

2015-07-21 10:50:34

我的错误是假设数组将在n中排序！尝试。如果是这样，n！/ 2将是一个有效的假设。我使用的洗牌代码应该是knuth-fisher-yates算法 – jogabonito

@jogabonito对不起，我的错误。你的洗牌功能很好。不过，你可以从1开始迭代'i'，因为每次都没有太多的交换'array [0]'。 –

洗牌代码测试

回答

相关问题