2008-10-07 23:17| 
10 Comments | 本文内容遵从 记得当年搞NOIp时，我犯过一个相当严重的错误：错误地把Floyd算法的i, j, k三层循环的位置顺序搞颠倒了。直到准备省选时我才突然意识到，Floyd算法应该最先枚举用于松驰操作的那个“中间变量”k，表示只经过从1到k的顶点的最短路；而我却一直习惯性地以为i, j, k应该顺次枚举。令人惊讶的是，这个错误跟了我那么久我居然从来都没有注意到过。后来，我发现有我这种经历的人不止一个。惯性思维很可能会让你接受一些明显错误的算法，并且让你用得坦坦荡荡，一辈子也发觉不了。
假使你需要把一个数组随机打乱顺序进行重排。你需要保证重排后的结果是概率均等、完全随机的。下面两种算法哪一种是正确的？其中，random(a,b)函数用于返回一个从a到b（包括a和b）的随机整数。
1. for i:=1 to n do swap(a[i], a[random(1,n)]);
2. for i:=1 to n do swap(a[i], a[random(i,n)]);
如果不仔细思考的话，绝大多数人会认为第一个算法才是真正随机的，因为它的操作“更对称”，保证了概率均等。但静下心来仔细思考，你会发现第二种算法才是真正满足随机性的。为了证明这一点，只需要注意到算法的本质是“随机确定a[1]的值，然后递归地对后n-1位进行操作”，用数学归纳法即可轻易说明算法的正确性。而事实上，这段程序一共将会产生n*(n-1)*(n-2)*...*1种等可能的情况，它们正好与1至n的n!种排列一一对应。
有人会问，那第一种算法为什么就错了呢？看它的样子多么对称美观啊……且慢，我还没说第一种算法是错的哦！虽然第一种算法将产生比第二种算法更多的可能性，会导致一些重复的数列，但完全有可能每种数列重复了相同的次数，概率仍然是均等的。事实上，更有可能发生的是，这两种算法都是正确的，不过相比之下呢第一种算法显得更加对称美观一些。为此，我们需要说明，第一种算法产生的所有情况均等地分成了n!个等价的结果。显然，这个算法将会产生n^n种情况，而我们的排列一共有n!个，因此n^n必须能够被n!整除才行（否则就不能均等地分布了）。但是，n!里含有所有不超过n的质数，而n^n里却只有n的那几个质因子。这表明要想n^n能被n!整除，n的质因子中必须含有所有不超过n的质数。这个结论看上去相当荒唐，反例遍地都是，并且直觉上告诉我们对于所有大于2的n这都是不成立的。为了证明这一点，只需要注意到2是质数，并且根据Bertrand-Chebyshev定理，在n/2和n之间一定还有一个质数。这两个质数的乘积已经大于n了。搞了半天，第一种看似对称而美观的算法居然是错的！
参考资料：http://adrianquark.blogspot.com/2008/09/how-to-shuffle-array-correctly.html
sf..
话说m67的floyd的确很强大的说
floyd??
还好刚学Floyd的时候就有人提醒我k在zuiwaiceng...
关于第一种“错误的”方案的研究，可以参考这篇 paper
http://arxiv.org/abs/math.CO/0010066/
它会导致 "For n equal to 18 or greater, the identity permutation is the most likely."
Floyd........
编错不知多少次了……但是改对之后也总忘- -
看懂了第二种，从来没想过这个问题。写的很好^_^
没懂最后两句话，不过前面都明白了。
我有一段时间没搞OI了，Floyd算法里面i、j、k循环顺序必须先k么？如果换了其他顺序正确性应该也能保证吧...
显然是第2种，“换好的不要动”是规矩……
[...] 一个有意思的情况出现了，这个算法和第三种算法非常相似，从直觉来说，似乎使数据“杂乱”的能力还要弱于第三种，但事实上，这种算法要强于第三种。要想严格的证明这一点并不容易，需要一些数学功底，有兴趣的朋友可以参照一下这篇论文，或者matrix67大牛的博文，也可以这样简单理解一下，对于n张牌的数据，实际排列的可能情况为n! 种，但第四种算法能够产生n^n种排列，远远大于实际的排列情况，而且n^n不能被n!整除，所以经过算法四所定义的牌与牌之间的交换程序，很可能一张牌被换来换去又被换回到原来的位置，所以这个算法不是最优的。而算法五输出的可能组合恰好是n!种，所以这个算法才是完美的。 事情并没有结束，如果真的要找一个最优的算法，还是请出最终的冠军吧！ [...]
看到lz用数学的方法证明第一种是错误的，真是强大。感觉很多人包括自己，数学都白学了，或者好像从来没学过数学。
如果从常理上考虑，所谓洗牌算法，是把某数组打乱重排，“保证重排后的结果是概率均等、完全随机的”，那么我们平时洗牌肯定是反复洗N多遍，然后一张一张的起牌，也就是一旦洗好，就不应该再动了。而第一种方法，就相当于我发了一张牌后，再找另外一副牌同样的一张放回去，然后再继续发牌，这样可能造成的一种情况就是，某些牌可能被多次“随机”处理，而某些牌根本得不到被“随机”处理的待遇，感觉不符合常识。