日期:2014-05-18  浏览次数:20809 次

随机洗牌的误区
假使你需要把一个数组随机打乱顺序进行重排。你需要保证重排后的结果是概率均等、完全随机的。下面两种算法哪一种是正确的?其中,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了。搞了半天,第一种看似对称而美观的算法居然是错的!

------解决方案--------------------
对,应该插入无序的那一堆,而不是全部。
------解决方案--------------------
确实是第二种算法才能保证各位置上的随机性,第一种算法非常明显会导致越靠后的位置不改变的几率越小。

第二种算法相当于从一个数组里随机抽取,并将结果存入第二个数组。可以做到每个位置上的几率完全相同。
------解决方案--------------------
不晓得你们直接有啥纠葛,不过第一个那个确实是错的,如果面试时给出来肯定要扣分的
------解决方案--------------------
第二种明显是对的。n!个组合,概率正好是1/n!。
第一种情况当n=2时是正确的!
------解决方案--------------------
那个问题我给出了2个解法;
用数组
C# code
        int[] numbers = new int[100];
        for (int i = 0; i < 100; i++)
            numbers[i] = i;
        Random rd = new Random();
        int index, realLength = numbers.Length, temp;
        for (int i = 0; i < 100; i++)
        {
            index = rd.Next(realLength);
            Response.Write(numbers[index] + "<br/>");
            temp = numbers[index];
            numbers[index] = numbers[realLength - 1];
            numbers[realLength - 1] = temp;
            realLength--;
        }

------解决方案--------------------
我不是很确定,但是帮lz问dalmeeme一个问题。

比如对1~10洗牌,洗牌足够多次,那么统计每个位置上出现某个数字应该都在1/10,是不是这样。

如果你有VS,可以统计下,就很简单了。


------解决方案--------------------
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)]);
推算:n=10;for(;i<=10;)
如果第二种,只要前面9个随机数有一个得10,那么肯定有重复了,因为第10个随机数必定是10,这样重复的机率更大,范围小了,随机的重复可能性更大,所以越后面,重复可能性越大,毫无交疑问的。

------解决方案--------------------
dalmeeme,我请教你一个问题。
产生100个[0-10)的随机整数,你看下面的算法是随机的么?(假设rnd(x, y)是随机的产生[x, y]的整数)

C# code
int[] result = new int[100];
for (int i = 0; i < 100; i++)
{
    if (i > 0)
    {
        if (result[i - 1] == 9) 
            result[i] = rnd(0, 9); 
        else 
            result[i] = rnd(result[i - 1] + 1, 9);
    }
    else
    {
        result[0] = rnd(0, 9);
    }
}

------解决方案--------------------
唉,技术论坛上何必吵架......

总不能去学那些口水论坛,没事就互相攻击着玩吧
------解决方案--------------------
C/C++ code
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int d[6];
int i,n,a,b,t;
int c,j;
void main() {
    srand(time(NULL));
    printf("shuffle 0..n-1 demo\n");
    for (n=1;n<=5;n++) {/* 测试1~5个元素 */
        printf("_____n=%d_____\n",n);
        j=1;
        for (c=1;c<=n;c++) j=j*c;/* j为n! */
        j*=n*2;
        for (c=1;c<=j;c++) {/* 测试n*2*n!次 */
            for (i=0;i<n;i++) d[i]=i;/* 填写0~n-1 */
            for (i=n;i>0;i--) {/* 打乱0~n-1 */
                a=i-1;b=rand()%i;
                if (a!=b) {t=d[a];d[a]=d[b];d[b]=t;}
            }
            printf("%04d:",c);
            for (i=0;i<n;i++) printf("%d",d[i]);