问题来源: 编程珠玑
解法一:
遍历这n个items，巧妙地利用概率来筛选
void
generate_random_m_from_n(int n, int m)
{
int i, remaining, select = m;
srand(time(NULL));
for(i=0; i<n; i++) {
remaining = n - i;
if(rand()%remaining < select) {
printf("%d\t", i);
--select;
}
}
printf("\n");
}
解法二:
shuffle，即随机洗牌程序，然后选择前m个items即可
代码参考:
http://blog.fuqcool.com/2011/04/17/algorithm-shuffle.html
作者：fuqcool 发布时间：2011-04-17 23:16:02 分类： algorithms
最近自己在做一个小的程序，需要把一个集合里面的元素全部随机地打散。自己想了一个方法，复杂度是n，觉得不太快。后来参照了一下python关于shuffle的算法，发现我的方法跟它的是一样的，连python的代码都这么写，可能已经没有办法再快了吧！
下面就来介绍洗牌算法，用C语言描述。
算法的前提是有一个产生随机数的函数
// Generates a random integer between beg and end.
int GetRandomNumber(int beg, int end);
还有一个交换函数。
// Swap a and b.
void Swap(int a, int b);
上面两个函数我就不写出实现了，因为这篇文章的重点在于算法的讨论。
假设我们有一堆扑克牌，怎么才能把这副牌完全打乱呢？计算机当然不能像人手那样洗牌。但是它可以产生随机数，随机地从一副牌中抽出一张牌是可以的。既然这样那就好办了，我们不停地从牌堆中随机抽取一张扑克牌，然后把这些牌堆起来，直到原来的牌堆只剩下一张牌的时候为止。这样不就完成了洗牌的动作了吗。
下面是C代码：
int Shuffle(int[] a, int len)
{
for (int i = len - 1; i > 0; i--)
{
// Select an element from index 0 to i randomly;
int index = GetRandomNumber(0, i);
// exchange a[i] with a[index]
Swap(a[index], a[i]);
}
}
顺便也贴出python的random单元关于shuffle的实现：
def shuffle(self, x, random=None, int=int):
"""x, random=random.random -> shuffle list x in place; return None.
Optional arg random is a 0-argument function returning a random
float in [0.0, 1.0); by default, the standard random.random.
"""
if random is None:
random = self.random
for i in reversed(xrange(1, len(x))):
# pick an element in x[:i+1] with which to exchange x[i]
j = int(random() * (i+1))
x[i], x[j] = x[j], x[i]