Question

“不重复的随机数”是否是真正的随机数？为什么？如果不是，又有什么价值？最好的生成算法是？

如题，经常可以看到网友有这种方面的需求。

Answer 1

不重复的是真正的随机数？这个问题的答案我觉得应该看具体你的需求是什么来决定。

以一个歌曲播放列表为例。

1. 如果想以随机顺序播放整个列表，但中途同一首歌只能播放一次，那这种情况的话就要求生成不重复的随机数。

2. 如果只是想随机播放歌曲，不关心是否一首歌重复播放，那就可以生成重复的随机数。

生成不重复的随机数的方法的话，以下C++代码是我目前所想的算是比较简便的。

随机生成不重复的0-100之间的数。生成个数和生成范围可自行调节。

以一个bitset来标记生成的随机数是否已经存在，存在就设为1，否则设为0。这样的话每次比较只用执行一次。

#include <iostream>
#include <ctime> 
#include <bitset>
using namespace std;

#define MAX 101

int main(void) 
{ 
	bitset <MAX> flag;
	srand((unsigned)time(NULL));

	for (int i = 0; i < MAX; ++i)
	{
		int val = rand() % MAX;
		if(!flag[val]) //not exist
		{
			printf("%3d ", val);
			flag.set(val);
		}
		else i--;
	}
	printf("\n");
	return 0; 
}

追问

理论性还是不够，另外上面的算法性能如何？也就是备选项越少，碰撞越大，如果性能要求极高，说不定在规定时间内找不到下一个随机数。

追答

虽然上面给的算法在存储空间上我觉得算挺好了，但是时间上的话应该是待改进的。虽然判断一个数是否合法时的比较操作只执行一次，时间复杂度为O(1)。但是正如你说的，备选项越少，碰撞大了以后，比较操作也会增加，时间复杂度分析就复杂了。我也学术浅薄，请原谅。
这种问题还是应该在英语论坛问才能得到满意答复。我暂且找到了一个相关问题，还没细读。可以的话你也可以看一下。
http://stackoverflow.com/questions/693880/create-random-number-sequence-with-no-repeats

追问

百度知道上应该没其他人来关注这个问题，至少你对我说的理解了。