编程珠玑——第十二章取样问题

问题1
    输入：包含两个整数m和n，其中m < n
    输出：0~n-1范围内的m个随机整数的有序列表，不允许重复
    从概率的角度说，希望得到没有重复的有序选择，其中每个选择出现的概率相等。
解答：
    该算法依次考虑整数0,1,2,......,n-1，并通过一个适当的随机测试对每个整数进行选择。通过按序访问整数，可以保证输出结果是有序的。
    为了理解选择的标准，考虑m = 2, n = 5的情况。选择第一个整数0的概率是2/5，可以通过下面的语句来实现。

 if(bigrand() % 5) < 2

    但是，我们不能以同样的概率选择来选择整数1：这样做的话，从5个整数里面选出的整数可能是两个也可能是不是两个。
    因此，决策有一些不同：在已经选择0的情况下以1/4的概率选择1，而在未选择0的情况下以2/4的概率选择1。
    一般说来，如果要从r个剩余的整数中选出s个，可以以概率s/r选择下一个数。

#include <iostream>
#include <algorithm>
#include <time.h>
using namespace std;

int bigrand()
{
    srand(unsigned(time(NULL)));
    return RAND_MAX *rand() + rand();
}

int randint(int l, int u)
{
    return l + bigrand() % (u - l + 1);
}

void getknuth(int m, int n)
{
    for(int i = 0; i < n; i ++)
    {
        //select m of remaining n - i
        if(bigrand() % (n - i) < m)
        {
            cout << i << " ";
            m--;
        }
    }
    cout << endl;
}

int main()
{
    int n = 10;
    int m = 5;
    getknuth(m, n);
    return 0;
}

    只要m <= n，选出的整数就恰好为m个：不会选择更多的数，因为m变为0时就不能再选择整数了；也不会选择更少的数，因为当m/n为1时一定会选中一个数。
    for循环语句确保按序输出所有的整数。每个子集被选中的可能性是相等的。

问题二
    上面的算法思想简单，代码很短，所需的空间少。但是算法的运行时间跟n成正比，因此，提出其他解决方案。
    方案一：
    在一个初始化为空的集合里面插入随机整数，直到个数足够。
    这里采用C++标准模板库，用set表示集合。

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

    该算法对每个元素的决策是一样的，输出是随机的。
    C++标准模板库规范每次插入都在O(logm)时间内完成，而遍历集合需要O(m)时间，因此此程序的时间复杂度为O(mlogm)（当m相对于n比较小时）。但是，该程序的空间开销比较大。

    方案二：
    生成随机整数的有序子集的另一种方法是把包含整数0~n-1的数组顺序打乱，然后把前m个元素排序输出。打乱n个元素可以采用如下方式。

for(int i = 0; i < n; i++）
{
     swap(i, randint(i, n - 1));
}

    这个问题只需要打乱数组的前m个元素即可。

void genshuf(int m, int n)
{
    int i, j;
    int *x = new int[n];
    for (i = 0; i < n; i++)
    {
        x[i] = i;
    }
    for (i = 0; i < m; i++)
    {
        j = randint(i, n-1);
        int t = x[i];
        x[i] = x[j];
        x[j] = t;
    }
    //排序
    sort(x, x+m);
    for (i = 0; i < m; i++)
    {
        cout << x[i] << " ";
    }
    cout << endl;
}

       该算法需要n个元素的内存空间和O(n+mlogm)的时间。该算法可以看作上面算法的变体：x[0....i-1]表示已经选中元素的集合，x[i....n-1]表示未选中的集合。通过显示的表示未选中的元素，就避免了对新元素是否已经选择的测试。