最初問題：從n個數中隨機選擇m個數(0<=m<=n)。
為了便于描述，可以將該問題抽象為：從0-n-1這n個數中隨機選擇m個數。計算機能夠提供的隨機數都是偽隨機的，我們假設計算機提供的偽隨機數為真正的隨機。
原創文章，轉載請注明出處：http://blog.csdn.net/fastsort/article/details/10162871
0、產生一個隨機數
系統(c/c++)提供的rand函數只有15位，如果不滿足要求，需要自己擴展，30位的隨機函數如下：
- /** @brief 返回一個30bit的隨機數
- ** @note 系統自帶的rand只有15bit
- */
- int BigRand()
- {
- static bool flag=false;
- if(flag==false)
- {
- srand(time(0));
- flag = true;
- }
- return (rand()<<15)+rand();
- }
1、最簡單的解法
每次產生一個0-n-1之間的隨機數，放入一個集合中，直到集合的大小為m。C++的STL中有set，比較方便：
- void GetRandNum_set(int m,int n)
- {
- cout<<__FUNCTION__<<": ";
- set<int> s;
- while(signed(s.size())<m)
- {
- s.insert(RandInt(0,n-1));
- }
- set<int>::iterator i=s.begin();
- while(i!=s.end())
- cout<<*i++<<" ";
- cout<<endl;
- }
如何不產生重復的數呢？
2、最多n次的解法
假設當前剩余m個數要選，
從0開始到n-1這n個數，以m/n的概率選中選中0：總共n個數，要選出m個；
對于1：如果選中0，則以(m-1)/(n-1)的概率選擇1（總共n-1個，要選m-1個）；如果沒選中，則以m/(n-1)的概率選（總共n-1個，要選m個）；
……
對于i：總共還剩下n-i個，還需要選m個，那么選中的概率就是m/(n-i)。
沒選中一個，剩余要選的數就減少一個。
因此代碼如下：
- /** @brief 在[0-n)中隨機的選擇m個不同的數
- ** 并按序輸出
- */
- void GetRandNumSorted(int m,int n)
- {
- cout<<__FUNCTION__<<": ";
- if(m<0 || m>=n) return;
- for(int i=0; m!=0 && i<n; i++)
- {
- if(BigRand()%(n-i)<m)
- {
- cout<<i<<" ";
- m--;
- }
- }
- cout<<endl;
- }
其中：if(BigRand()%(n-i)<m) 的概率為：m/(n-i)。
可以分析，每個數選中的概率都是m/n：
數 選中概率
0： m/n
1: m/n * (m-1)/(n-1) + (1-m/n) * m/(n-1) =m/n;
2: 好多項相加，這里就不寫了。。。
……
3、不按序輸出
如果要求不按序輸出，有兩種解決辦法。
一種是將上面的結果保存起來，然后再打亂保存的數組。
還有一種就是直接產生m個隨機數。
先看直接產生m個隨機數，其實就是先從0-n-1中隨機選擇一個，作為第一個；然后再從剩下的n-1個數中隨機選擇一個作為第二個……直到選出第m個。這就是所謂“完美洗牌”或者打亂數組。
- /** @brief 在[0-n)中隨機的選擇m個不同的數
- ** 并隨機輸出
- */
- void GetRandNum(int m, int n)
- {
- cout<<__FUNCTION__<<": ";
- int * p= (int*)malloc(sizeof(int)*n);//!!!
- for(int i=0;i<n;i++)
- p[i] = i;
- ///shuffle p[0...m-1]
- for(int i=0; i<m; i++)
- {
- swap(p[i],p[RandInt(i,n-1)]);
- cout<<p[i]<<" ";
- }
- cout<<endl;
- free(p);
- }
這里需要一個函數，能夠隨機產生一定范圍內的數：
- /** @brief 返回[l,u]之間的一個隨機數 **/
- int RandInt(int l, int u)
- {
- l = l<u?l:u;
- u = l<u?u:l;
- return BigRand()%(u-l+1) + l;
- }
這種算法的問題是，如果n很大，m很小，對輔助空間的浪費太嚴重。因為開辟了那么大的空間，實質只用了很少一部分。
另一種就是先按序隨機選擇m個數，然后再打亂：
- /** @brief 在[0-n)中隨機的選擇m個不同的數
- ** 并隨機輸出
- */
- void GetRandNum2(int m, int n)
- {
- cout<<__FUNCTION__<<": ";
- int * p= (int*)malloc(sizeof(int)*m);
- int tm=m;
- for(int i=0,j=0; m!=0 && i<n; i++)
- {
- if(BigRand()%(n-i)<m)
- {
- p[j++]=i;//cout<<i<<" ";
- m--;
- }
- }
- for(int i=0; i<tm; i++)
- {
- swap(p[i],p[RandInt(i,tm-1)]);
- cout<<p[i]<<" ";
- }
- cout<<endl;
- free(p);
- }
4、隨機讀取文件中的一行
在不知道文件總行數的情況下，隨機讀取文件中的一行。
最直觀的做法就是，先讀取一次文件，確定總行數n。然后產生一個1-n的隨機數m，再讀取第m行。顯然這是可行的，但是問題是如果文件很大，平均要遍歷文件1.5次。效率很低。
而且如果文件在不算增長，那么這個方法就不行了。
通過上面的算法的啟發，其實也可以只讀取一次。
首先讀取第一行，如果只有一行，就結束了，設為line；
如果有第2行，那么以1/2的概率替換line；這時1、2兩行被選中的概率都是1/2.
如果有第3行，那么以1/3的概率替line；則第3行被選中的概率是1/3，1、2兩行被選中的概率則都是1/2*2/3=1/3.
……
第i行，以1/i的概率替換line。
直到文件結束。
- /** @brief 從文件fname中隨機讀取一行 */
- void GetOneLineRand(const char *fname)
- {
- cout<<__FUNCTION__<<": ";
- string line,str_save;
- ifstream ins(fname);
- int cnt=1;
- while(getline(ins,line))
- {
- if(cnt==1)
- {
- str_save = line;
- }
- else
- {
- if(RandInt(1,cnt)==1)///[1,cnt]
- str_save = line;
- }
- cout<<cnt<<" : "<<line<<endl;
- cnt++;
- }
- cout<<"rand line : "<<str_save<<endl;
- ins.close();
- }
5、隨機讀取k行
先去讀k行，保存在一個數組中（假設文件至少有k行）；
然后每讀取一行，都以k/n的概率替換數組中的任意一行，其中n為當前總共讀取的行數。
- /** @brief 從文件fname中隨機讀取k行
- */
- void GetRandLines(const char *fname, int k)
- {
- cout<<__FUNCTION__<<": ";
- string * kstr = new string[k], line;
- ifstream ins(fname);
- int cnt=1;
- while(cnt<=k)///先讀取前k行
- {
- if(getline(ins,kstr[cnt-1])) cnt++;
- else break;///文件沒有k行，直接退出
- }
- while(getline(ins,line))
- {
- if(RandInt(1,cnt)<=k)/// p=k/cnt
- {
- swap(kstr[RandInt(1,k)-1],line);///隨機替換一行
- }
- cnt++;
- }
- for(int i=0; i<k ;i++)
- {
- cout<<kstr[i]<<endl;
- }
- cout<<endl;
- delete[] kstr;
- ins.close();
- }
其他問題請參考《編程珠璣-第12章》。
原創文章，轉載請注明出處：http://blog.csdn.net/fastsort/article/details/10162871
文章列表
留言列表
