取樣問題

取樣問題

本章講述了一個(gè)小的隨機(jī)抽樣問題，并用不同的方法來解決它。

問題：對于整數(shù)m和n，其中m<n，輸出0~n-1范圍內(nèi)m個(gè)隨機(jī)整數(shù)的有序列表， 不允許重復(fù)。

比如m=3, n=5，那么一種可能輸出是0，2，3(要求有序)。實(shí)現(xiàn)1來自Knuth的TAOCP， 時(shí)間復(fù)雜度O(n)：

void GenKnuth(int m, int n) {
    for(int i=0; i<n; ++i) {
        if((bigrand()%(n-i)) < m) {
            cout<<i<<endl;
            --m;
        }
    }
}

其中，bigrand()的作用是返回一個(gè)很大的隨機(jī)整數(shù)。

實(shí)現(xiàn)2：在一個(gè)初始為空的集合里面插入隨機(jī)整數(shù)，直到個(gè)數(shù)足夠。代碼如下：

void GenSets(int m, int n) {
    set<int> s;
    while(s.size() < m)
        s.insert(bigrand() % n);
    set<int>::iterator i;
    for(i=s.begin(); i!=s.end(); ++i)
        cout<<*i<<endl;
}

實(shí)現(xiàn)3：把包含整數(shù)0～n-1的數(shù)組順序打亂，然后把前m個(gè)元素排序輸出。 該方法的性能通常不如Knuth的算法。代碼如下：

void GenShuf(int m, int n) {
    int x[n];
    for(int i=0; i<n; ++i)
        x[i] = i;
    for(int i=0; i<m; ++i) {
        int j = randint(i, n-1);
        swap(x[i], x[j]);
    }
    sort(x, x+m);
    for(int i=0; i<m; ++i)
        cout<<x[i]<<endl;
}

深入閱讀：Don Knuth的《The Art of Computer Programming, Volume 2: Seminumerical Algorithms》