随机洗牌:哪一种算法是正确的?

    记得当年搞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

18 条评论

  • Assassin.cpy.pku

    sf..
    话说m67的floyd的确很强大的说

  • sqybi

    还好刚学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.”

  • uchihatmtkinu

    Floyd……..
    编错不知多少次了……但是改对之后也总忘- –

  • Greenmoon55

    看懂了第二种,从来没想过这个问题。写的很好^_^
    没懂最后两句话,不过前面都明白了。

  • Eagle_Fantasy

    我有一段时间没搞OI了,Floyd算法里面i、j、k循环顺序必须先k么?如果换了其他顺序正确性应该也能保证吧…

  • prob.

    显然是第2种,“换好的不要动”是规矩……

  • 荆棘路

    看到lz用数学的方法证明第一种是错误的,真是强大。感觉很多人包括自己,数学都白学了,或者好像从来没学过数学。

    如果从常理上考虑,所谓洗牌算法,是把某数组打乱重排,“保证重排后的结果是概率均等、完全随机的”,那么我们平时洗牌肯定是反复洗N多遍,然后一张一张的起牌,也就是一旦洗好,就不应该再动了。而第一种方法,就相当于我发了一张牌后,再找另外一副牌同样的一张放回去,然后再继续发牌,这样可能造成的一种情况就是,某些牌可能被多次“随机”处理,而某些牌根本得不到被“随机”处理的待遇,感觉不符合常识。

  • Lamdy

    For i = 51 To 1 Step -1
    If Rnd * (i + 1) > 1 Then
    j = Int(Rnd * i)
    a(i) = a(i) Xor a(j)
    a(j) = a(i) Xor a(j)
    a(i) = a(i) Xor a(j)
    End If
    Next

  • trif

    随机和等可能是两回事吧

  • trif

    随机和等可能是两回事吧
    还有n^n不能被n!整除应该很好证啊,n^n=1(mod n-1)

  • cervelo

    真是强大。感觉很多人包括自己,数学都白学了,或者好像从来没学过数学。

  • fq1

    for i:=1 to n do swap(a[i], a[random(0,i)]);
    请问这种算法是否正确,是否与第二种算法等价?
    参考:http://bbs.csdn.net/topics/390586742

  • Jokeren

    今天才看到,好文!

发表评论