問(wèn)題來(lái)源: 編程珠璣
解法一:
遍歷這n個(gè)items，巧妙地利用概率來(lái)篩選
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，即隨機(jī)洗牌程序，然后選擇前m個(gè)items即可
代碼參考:
http://blog.fuqcool.com/2011/04/17/algorithm-shuffle.html
作者：fuqcool 發(fā)布時(shí)間：2011-04-17 23:16:02 分類： algorithms
最近自己在做一個(gè)小的程序，需要把一個(gè)集合里面的元素全部隨機(jī)地打散。自己想了一個(gè)方法，復(fù)雜度是n，覺(jué)得不太快。后來(lái)參照了一下python關(guān)于shuffle的算法，發(fā)現(xiàn)我的方法跟它的是一樣的，連python的代碼都這么寫(xiě)，可能已經(jīng)沒(méi)有辦法再快了吧！
下面就來(lái)介紹洗牌算法，用C語(yǔ)言描述。
算法的前提是有一個(gè)產(chǎn)生隨機(jī)數(shù)的函數(shù)
// Generates a random integer between beg and end.
int GetRandomNumber(int beg, int end);
還有一個(gè)交換函數(shù)。
// Swap a and b.
void Swap(int a, int b);
上面兩個(gè)函數(shù)我就不寫(xiě)出實(shí)現(xiàn)了，因?yàn)檫@篇文章的重點(diǎn)在于算法的討論。
假設(shè)我們有一堆撲克牌，怎么才能把這副牌完全打亂呢？計(jì)算機(jī)當(dāng)然不能像人手那樣洗牌。但是它可以產(chǎn)生隨機(jī)數(shù)，隨機(jī)地從一副牌中抽出一張牌是可以的。既然這樣那就好辦了，我們不停地從牌堆中隨機(jī)抽取一張撲克牌，然后把這些牌堆起來(lái)，直到原來(lái)的牌堆只剩下一張牌的時(shí)候?yàn)橹埂＿@樣不就完成了洗牌的動(dòng)作了嗎。
下面是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單元關(guān)于shuffle的實(shí)現(xiàn)：
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]