取样问题

    前段时间，一同学让我帮他实现一个抽奖系统，花了2天时间写了一个，不是很复杂。既然是抽奖，那必然是涉及到取样问题，如何在最短时间內对样本中的元素以等概率进行选取，这里的要求就是不能重复，也就是说不可能一个人既中一等奖也中了二等奖。
    让我把这个问题在抽象一下，给定一个含M个元素的数组，从中抽取N个元素（N方案一：
    第一反应：利用随机数，每次选取一个元素，判断该元素是否已经选取过，如果是，重新选取，否则，输出。进行下一轮选取。
    方案一确实能解决这个问题，这里我们再加一个限制，按序输出。或许，有人会说，这还不简单，选取的元素不直接输出，而是存放到一个数组中，选取结束之后，先排序，再输出。这样确实也可以，而我从另一个角度来出发。
   方案二：
   前面是把N个元素作为分析对象，现在我们把M个元素作为分析对象，那么，对于M中的每一个元素被选的概率为N/M，那么我们就可以对这M个元素按序作概率选取，这样我们就能保证其结果是按序输出的。C语言实现如下：

#define M 2000
#define N 5
int myrand()
{
    int n = rand()%M;
    if(n < N)
        return 1;
    return 0;
}

int main()
{
    int i=0, j=0;
    srand(time(NULL));
    for(i=0; i<M; i++)
    {
        if(myrand() == 1)
            printf("%d ", i);
    }
    return 0;
}

    等等，这里似乎有点问题，比如，现在有2个元素，要选取一个。对于第一个，选取的概率为0.5，如果第一个没选中，那么第二个元素必然要选中，但此时，第二个元素被选取的概率仍为0.5，所以这里的代码执行结果就是选取的元素可能是N个，也可能小于N个，也有可能大于N个。
    所以，我们不能以等概率来选取每一个元素，比如，5个元素中选取2个，第一个被选取的概率为0.4，如果第一个没有选中，那么第二个被选取的概率应该为0.5（2/4），如果第一个选中了，那么第二个被选取的概率为0.25(1/4)。如果学过概率论的话，其实每个元素被选取的概率仍然是等概率的。C语言实现如下：

#define M 2000
#define N 5
int myrand(int m, int last)
{
    int n = rand()%m;
    if(n < last)
        return 1;
    return 0;
}

int main()
{
    int i=0, j=0;
    int remaining = N, selected = 0;
    srand(time(NULL));
    for(i=0; i<M; i++)
    {
        if(myrand(M-i-selected, remaining) == 1)
        {
            printf("%d ", i);
            selected++;
            remaining--;
            if(remaining == 0)
                break;
        }
    }
    return 0;
}

方案三：
   我们仍以M个元素作为分析对象，选取N个元素的过程我们可以看成是将M个元素顺序打乱后，输出的前N个，比如，M个元素有M！种排列方式，我们随机选取其中一种，输出其前N个元素。
   这里可以做一下简化，我们只需要打乱前N个元素即可，打乱后，将前N个元素排序输出。C语言实现如下：

#define M 2000
#define N 5

int randint(int start, int end)
{
    return rand()%(end-start) + start;
}
int com(const void *a, const void *b)
{
    int *aa = (int *)a, *bb = (int *)b;
    if(*aa > *bb)    return 1;
    else if(*aa == *bb)    return 0;
    else if(*aa < *bb)    return -1;
}
int main()
{
    int i=0, j;
    int *a = (int *)malloc(M*sizeof(int));
    int temp;
    srand(time(NULL));
    for(i=0; i<M; i++)
        a[i] = i;
    for(i=0; i<N; i++)
    {
        j = randint(i, M-1);
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    qsort(a, N, sizeof(int), com);
    for(i=0; i<N; i++)
        printf("%d ", a[i]);
    printf("\n");
    free(a);
    return 0;
}

   其实关于取样问题还有很多方法，每种方法都适用于特定的问题，我们只有在深入理解问题的情况下，才有可能设计出高效的代码。