或者说是加权随机选取问题，问题是这样的：
n个数，每个数都有权重值，权重值高的，意即该数应该出现的概率大；要求要从n个数中根据各数的权重值随机选取m个数。例如以下10个数：
1(0.1), 2(0.2), 3(0.3), 4(0.4), 5(0.5), 6(0.6), 7(0.7), 8(0.8), 9(0.9), 10(1.0)
括号内的数字表示其权重值，要求根据各数的权重值从这10个数中随机选择3个数。
最容易想到的算法是将这些权重值累加起来，得到一根长度为a的线段，每个权重值是其中的一部分，权重值大的，则它对应的子线段的长度就长。产生随机数r(0,a)，即0到a之间的随机数，然后判断这个随机数落在哪个子线段中，就将其选中。
这种思路出发点是：权重高的数，随机数r落在其对应的子线段的概率就大，因为其对应的线段较长。
但是以上算法在用计算机实现时，比较麻烦的，复杂度为m*n。如果再加一个限制，随机取出来的元素不允许重复，那时间复杂度就更高了。
后来在一个paper上看到一算法，完全是数学的方法：
http://utopia.duth.gr/~pefraimi/research/data/2007EncOfAlg.pdf
，我写成了程序，运行的效果不错。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <limits.h>
#include <vector>
#include <algorithm>
typedef long ELEM_TYPE;
#define RAND_LESS_1 (rand() / (float)INT_MAX)
using namespace std;
static bool
weigth_compare(pair<float, int>& a,
pair<float, int>& b)
{
bool ret = false;
if (a.first > b.first)
ret = true;
return ret;
}
/**
* weighted random sampling
*/
void
weighted_random(ELEM_TYPE* v,
float* w,
int v_size,
vector<ELEM_TYPE>& r,
int r_size)
{
vector<pair<float, int> > vv;
r_size = r_size <= v_size ? r_size : v_size;
for(int i = 0; i < v_size; i++)
{
float u = RAND_LESS_1;
float w_i = 1 / *(w + i);
float k = pow(u, w_i);
/*
fprintf(stdout, "rand less 1:%f, w_i:%f, k:%f\n",
u, w_i, k);
*/
vv.push_back(make_pair(k, i));
}
partial_sort(vv.begin(),
vv.begin() + r_size,
vv.end(),
weigth_compare);
for(int i = 0; i < r_size; i++)
r.push_back(v[vv[i].second]);
}
int main(int argc, char** argv)
{
srand(time(NULL));
ELEM_TYPE v[] = {1, 2, 3, 4, 5, 6, 7, 8};
float w[] = {1, 2, 3, 4, 5, 6, 7, 8};
int v_size = 8;
vector<ELEM_TYPE> r;
int r_size = 3;
for (int i = 0; i < 30; i++)
{
r.clear();
weighted_random(v, w, v_size, r, r_size);
fprintf(stdout, "%ld, %ld, %ld\n", r[0], r[1], r[2]);
}
return 0;
}
