一、简介
问题描述：程序的输入包含两个整数m和n，其中m<n。输出是0~n-1范围内m个随机整数的有序列表，不允许重复。从概率的角度说，我们希望得到没有重复的有序选择，其中每个选择出现的概率相等。
（1）一般情况下，如果要从r个剩余的整数中选出s个，我们以s/r的概率来选择下一个数。如下伪代码所示：
select = m
remaining = n
for i = [0, n)
if (bigrand() % remaining) < select
print i
select—
remaining--
下面给出一个C++的实现：
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;
}
（3）另一个解决方法是在一个初始为空的集合里插入随机整数，直到个数足够。伪代码如下：
initialize set S to empty
size = 0
while size < m do
t = bigrand() % n
if t is not in S
insert t into S
size++
print the elements of S in sorted order
利用C++的标准模板库实现如下所示：
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;
}
（3）生成随机整数的有序子集的另一种方法时把包含整数0~n-1的数组顺序打乱，然后把前m个元素排序输出即可。
for i = [0, n) swap(i, randint(i, n-1) ) // randint(i, j)从i...j范围内均匀选择的随机整数的函数
其实在这个问题中，我们只需要打乱数组的前m个元素，对应的C++代码如下所示：
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;
}
//排序数组中的前m个元素
sort(x, x+m);
for (i = 0; i < m; i++)
{
cout << x[i] << " ";
}
cout << endl;
}
二、原理
（1）正确理解所遇到的问题，即将问题抽象成能用数学或逻辑表示的命题；
（2）提炼出抽象问题，有助于我们把解决方案应用到其他问题中；
（3）考虑尽可能多的解法，多思考，然后会发觉写代码的时间会很短；
（4）实现一种解决方案。
三、习题
1、C库函数rand()通常返回约15个随机位，使用该函数实现函数bigrand()和randint(l,u)，前者返回至少30个随机位，后者返回[l,u]范围内的一个随机整数，解答如下：
int bigrand()
{
return RAND_MAX*rand() + rand();
}
int region(int l, int u) //[l, u]
{
return l + rand() % (u - l + 1);
}
2、当m接近于n时，就集合的算法生成的很多随机数都要丢弃，因为他们之前已经存在于集合中了。能否给出一个算法，使得即使在随坏情况下也能使用m个随机数？
#include <iostream>
#include <set>
using namespace std;
void getSet(int m,int n)//在0 -- n-1 中挑选m个 随机数
{
srand(time(NULL));//这个很关键
set<int> S;
for(int i=n-m;i<n;++i)
{
int t=rand()%(i+1);
if(S.find(t) == S.end())
S.insert(t);
else
S.insert(i);
}
set<int>::iterator j;
for(j=S.begin();j!=S.end();++j)
cout<<*j<<" ";
}
int main()
{
getSet(5,10);
return 0;
}
3、如何从n个对象中随机选择一个？具体说来，如何在实现不知道文本文件行数的情况下读取该文件，从中随机选择并输出一行？
我们总是选择第一行，并用二分之一的概率选择第二行，使用三分之一的概率选择第三行，以此类推。在该过程结束的时候，每一行具有相同的选中概率（1/n，其中n是文件的总行数）：
i = 0
while more input lines
with probability 1.0/++i
choice = this input line //如果前面做了选择，并不会break，而是直到最后一个为止。
print choice
这里比较有些疑惑的是第一行：总是选第一行 为什么概率还是1/n？
概率=1*(1/2)*(2/3)*(3/4)……(n-1/n) =1/n。
证明：当做第i步选择（选择第i行）时，选择该行的概率为1/i，则不选择的概率为(i-1)/i，对于一篇有n行的文档，现需证明最终选定第i行的概率为1/n。
当最终选择第i行，前（i-1）步的选择对最终结果不会产生影响，第i步选择的概率为1/i，即选择第i行，第（i+1～n）步中均采取不选择的动作，即对于任意j(i+1<=j<=n)，当前步的概率为(j-1)/j，那么最终的概率为：(1/i)*((i)/(i+1))*...*((n-1)/n) = 1/n。
以一篇只有6行的文档为例，最终选择第2行的概率为：1/2*(2/3)*(3/4)*(4/5)*(5/6) = 1/6。
扩展：原问题可简化为：如何从n个有序对象中等概率地任意抽取1个，简记为sample（n,1），其中n未知；
若将该问题改为：如何从n个有序对象中等概率地任意抽取m个，简记为sample（n,m），其中n未知；
分析：若n已知，sample(n,m)是普通的抽样问题；当n未知时，可否根据上述算法进行相应的转化求解？
解决方案：将sample(n,m)问题转化为m个sample(n,1)问题，更具体一点是，转化为sample(n,1);sample(n-1,1);sample(n-2,1)....;sample(n-m+1,1)问题。
仍然以一篇6行文档为例，任取其中2行，做法如下：
第一遍，以如下概率选中一行：1(1) 2(1/2) 3(1/3) 4(1/4) 5(1/5) 6(1/6)，假设选中第2行，接着概率修改如下：3(1) 4(1/2) 5(1/3) 6(1/4) 1(1/5)。
说明：当选中第2行，从第3行开始修改概率，并将第2行排除在外，继续扫描，这样能保证在剩下的5个数中仍然以等概率抽取其中的一个。