原文地址:
http://www.blogjava.net/lhulcn618/archive/2010/02/21/313522.html
需求描述:从 0 到 n 之间选 k 个不重复的数组成一个序列。
伪代码如下:
1 | for(i = 0; i < n; 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]中存着呢,所以被选中的概率相等。
最后附上 Java 实现:
1 | public static void generateRandomNum(int count, int max) { |
PS: 后来我发现 Java 的 Collections.shuffle() 方法的实现,也是采用的这个算法。看来这个算法是相当的经典啊!