分类： C/C++
2011-12-25 15:05:56
问题描述：
现要求产生 0~n-1 范围内的 m 个随机整数的有序列表，且不允许重复，m <= n。
转自://blog.csdn.net/huagong_adu/article/details/5572637
考虑到 n 的值可能很大，而通常 C/C++ 提供的随机数产生器所能返回的随机数在 [0,RAND_MAX]，其中，RAND_MAX 为 0x7FFF。也就是说只有 15 位的随机性。因此，我们需要要有自己的随机数产生器，以便能够返回更多位数的随机数，通常为 30 位。下面的函数可以满足我们的要求：
int bigrand()
{
return (RAND_MAX * rand() + rand());
}
注意，这里也可以采用将第一个 rand() 的返回值左移 15 位，然后加上第二个 rand() 的返回值的方法来提速。
解法一、
下面，我们就可以用这个随机数产生器来解决上面的问题了。看到这里，你是不是想到了什么解决方法呢。下面的方法来自算法大师 Donald Knuth。
void genknuth(int m, int n)
{
if(0 == m) return;
srand((unsigned int)time(NULL));
for(int i = 0; i < n; i++)
{
if((rand() % (n - i)) < m)
{
printf("%4d\n", i);
m--;
}
}
}
其中的 srand 语句是我为了在每次运行时能够得到不同的随机数序列而加的。
不知道这个方法有没有出乎你的意料，算上 for 循环才 4 句话。不过，就是这 4 句话，已经很完美地解决了上面提出的问题，有序、互异、m 个数。
这个方法通过顺序扫描 0~n-1 范围内的每个数保证产生的随机数有序和互异。
那产生 m 个数怎么保证呢？又没有类似循环的语句来控制产生的随机数的个数。
要记住，程序语句只是我们实现某种功能的一种表现形式，这也就是说，我们要实现某种功能，可以由很多种表现形式。下面就来分析一下这个方法是如何保证能够产生 m 个随机数的。
想必大家都已经看到产生的随机数都是在 if 语句中输出的，那也就是说 if 语句控制了产生的随机数的个数。因此，要说明能够产生 m 个随机数，只要说明 if 语句能够执行且仅能执行 m 次。
首先，在 for 循环没有推出的情况下，if 语句最多能够执行 m 次，因为 if 语句的每次执行都会使 m 的值减 1，当 m=0 时，if 语句就不会再执行了。因为 (rand() % (n - i)) 是一个非负数。
其次，我们分析 if 语句最少能够执行多少次。如果 if 语句开始一直得不到执行，那么 (n-i) 便会一直减小，直到与 m 相等。这时 (rand() % (n - i)) 一定小于 (n-i)，也就是 m，从而使得 if 语句得到一次执行。而此时 for 循环已经执行了 (n-m+1) 次，离推出循环只剩下 (m-1) 次，要使得 if 语句能够执行 m 次，那么接下来的 (m-1) 次循环 if 语句必须都得能够执行。事实是什么样的呢？第一次 if 语句开始执行时，(n-i)=m，执行完时，(n-i) 和 m 都减少 1，从而仍然有 (n-i)=m 成立。这个过程一直持续到 m=0。刚好是 m-1 次。
我的理解：因为rand()%value的值是(0, value-1)，把这个运算看做select [0, value) 。
一般n>>m，所以n-i=value一开始也比m大，那么在(0, value)中通过rand运算找出一个小于m的数的机会很多，因为每次都可以从大数一直找到0。如果rand运算没有找到小于m的数(毕竟是random select)，那么由于 i 的增大，value将一直减小到m，这时继续select[0, value) 就相当于select[0, m)，随便怎么rand()%结果都是小于m的，而且接下来的每次也都是小于m的。
因此，我们可以相信 if 语句确实能够执行且只能执行 m 个。
Donald Knuth 实在是太厉害了！
顺便说一句，据说在大学期间，有关程序设计之类的比赛，只要有他参加，第一名非他莫属。
解法二、
就是在一个初始为空的集合中插入随机整数，直到足够的整数。
伪代码如下所示：
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
该算法在选择元素时能够保证所有的元素都具有相同的选中概率，它的输出是随机的
void genknuth(int m, int n)
{
set
while( S.size() < m)
S.insert(bigrand()%n);
set
for(i = S.begin(); i != S.end(); ++i)
cout<<*i<<"/n";
}
C++标准模板库规范能够保证在O（log m)时间内完成每个插入操作，集合内部迭代需要O(m),所以整个程序需要的时间为O(m log(m)(和n相比，m较小时）。然而，该数据结构的空间消耗较大。
解法三、
for i = [0,n)
swap(i, randint(i,n-1))
这个是弄乱数据x[0...n-1]。在这个问题中，只需要搅乱数组前面m个元素
int bigrand()
{
return RAND_MAX*rand() + rand();
}
int randint(int l, int u)
{
return l + bigrand() % (u-l+1);
}
void genknuth(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);
swap(x[i],x[j]);
}
sort(x, x+m);
for(i=0; i
cout<
}
int main()
{
srand((unsigned)time(NULL));
int m,n;
while(1)
{
cout<<"Please enter m and n:";
cin>>m>>n;
genknuth(m,n);
}
return 0;
}
该算法使用了n个字的内存并需要O(n+mlogm)时间
解法四、
递归
void randselect(int m,int n)
{
assert(m>=0 && m <= n);
if(m>0)
if((bigrand()%n) < m)
{
randselect(m-1,n-1);
cout<
}
else
randselect(m, n-1);
}
原文链接：
http://blog.csdn.net/ztj111/archive/2007/10/23/1840190.aspx
http://hi.baidu.com/xwf_like/blog/item/ff2a9b98293022006e068c2d.html
