随笔-159  评论-114  文章-7  trackbacks-0
这个需求应该是很常见的吧,需要从 0 到 n 之间选 k 个不重复的组成一个序列。

我最早遇到这个问题是在给校ACM比赛出题时,需要随机产生一些测试数据,当时我想的是用一个辅助数组记录之前已经产生的随机,如果当前产生的随机已经出现过就再重新随机

显然这样的实现效率是很低的,设想从10000个随机产生10000个的序列,当前面9999个已经确定了时,最后一个随机到的概率是 0.0001,也就是说大概需要调用随机函数10000才会产生。类似的,第9999个随机到的概率是0.0002……
.....

我后来采用了一个改进的办法是,如果当前产生的随机a已经在之前产生过了,就顺序去找比a小的,直到找到一个之前没有产生过的,如果找不到就找比a大的

可以看到这样的改进节省了大量的时间,但是这样产生的已经不是随机序列了!

试想从1,2,3,4中随机挑选2个,假如第一次选出来的是3,那么第二再选的话,选中2的概率就变成了1/2,因为当随机出来的为2或3时,我们都选择2。

在我遇到的应用中,因为对随机序列的“随机性”要求不是很高,所以凑合着用了上述办法。

直到今天在《Programming pearls》里看到这个很完美的办法:
for(i = 0; i < n; i++)
{
x[i] = i;
}
for(i = 0; i < k; i++)
{
t = rand(i,n-1);
swap(x[i], x[t]);
out(x[i]);
}

其中,rand(a,b)产生一个 a 到 b 之间的随机,swap(a,b)交换a和b的值,out(a)把a输出作为结果。
我们来看看这个算法的完美之处吧!

首先,x数组里把0到n-1的所有都存储了,而最后输出的都是x数组里的值,所以满足输出的是k个0到n-1的

然后,我们对于第 i 随机,产生一个 i 到 n-1 的下标 t ,并把x[t] 和x[i]交换,将其输出,这样每产生的都是之前没有出现过的,因为之前出现过的都在x[0] 到 x[i-1]里呢!这样就保证了输出数据的不重复性。

最后,我们考察输出数据的“随机性”,显然,因为交换操作,使得所有没有出现过的都在x[i] 到 x[n-1]中存着呢,所以被选中的概率相等。


写完上面这些文字之后,我在想,这样经典的算法,应该是早就已经出现了,但是我竟然还不知道,这样看来,我百度实习面试遭鄙视也就是很自然的了,这也算是我之前的一个毛病,喜欢遇到问题才去想怎么解决,没问题就很少看相关的书或资料,而对于自己能解决的问题(比如上面说的这个凑合着能用的问题),我又懒得去找更好的甚或是标准的解决方法,所以才造成了我现在的知识局限,以后要多看书,多想问题,尽量多的积累知识吧……


posted on 2010-02-21 14:21 北国狼人的BloG 阅读(4118) 评论(1)  编辑  收藏

评论:
# re: 高效产生一组不重复的随机数 2013-08-12 18:11 | ll
要是要求产生的随机数量特别大怎么办啊  回复  更多评论
  

只有注册用户登录后才能发表评论。


网站导航: