问题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
因此，决策有一些不同：在已经选择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;
- }
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));
- }
-
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;
- }