这个需求应该是很常见的吧，需要从 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 阅读(4123)
评论(1) 编辑 收藏