《不重复随机数列生成算法.pdf》由会员分享，可在线阅读，更多相关《不重复随机数列生成算法.pdf（5页珍藏版）》请在三一文库上搜索。
1、不重复随机数列生成算法 本文将讲述一个高效的不重复随机数列的生成算法，其效率比通常用hashtable 消重的方法要快很多。 作者： eaglet 转载请注明出处。 首先我们来看命题： 给定一个正整数 n，需要输出一个长度为n 的数组，数组元素是随机数，范围为 0 n-1 ，且元素不能重复。比如 n = 3 时，需要获取一个长度为3 的数组， 元素范围为 0-2， 比如 0,2,1 。 这个问题的通常解决方案就是设计一个 hashtable ，然后循环获取随机数，再 到 hashtable 中找，如果 hashtable 中没有这个数，则输出。下面给出这种算 法的代码 publicstatic
2、int GetRandomSequence0(int total) int hashtable = new int total; int output = new int total; Random random = new Random(); for ( int i = 0; i 0) num = random.Next(0, total); outputi = num; hashtablenum = 1; return output; 代码很简单，从 0 到 total - 1 循环获取随机数，再去hashtable 中尝试匹 配，如果这个数在hashtable 中不存在，则输出，并把这个
3、数在hashtable 中 置 1，否则循环尝试获取随机数， 直到找到一个不在hashtable 中的数为止。 这 个算法的问题在于需要不断尝试获取随机数，在hashtable 接近满时，这个尝 试失败的概率会越来越高。 那么有没有什么算法，不需要这样反复尝试吗？答案是肯定的。 如上图所示，我们设计一个顺序的数组，假设n = 4 第一轮，我们取 0 3 之间的随机数，假设为2，这时，我们把数组位置为2 的数取出来输出，并把这个数从数组中删除，这时这个数组变成了 第二轮，我们再取 0-2 之间的随机数，假设为1，并把这个位置的数输出，同 时把这个数从数组删除，以此类推，直到这个数组的长度为0。这
4、时我们就可以 得到一个随机的不重复的序列。 这个算法的好处是不需要用一个hashtable 来存储已获取的数字，不需要反复 尝试。算法代码如下： publicstaticint GetRandomSequence1(int total) List input = new List(); for ( int i = 0; i output = new List(); Random random = new Random(); int end = total; for ( int i = 0; i / Designed by eaglet / / / publicstaticint GetRand
5、omSequence2(int total) int sequence = new int total; int output = new int total; for ( int i = 0; i total; i+) sequencei = i; Random random = new Random(); int end = total - 1; for ( int i = 0; i total; i+) int num = random.Next(0, end + 1); outputi = sequencenum; sequencenum = sequenceend; end-; return output; 下面是 n 等于 1 万，10 万和 100 万时的测试数据，时间单位为毫秒。从测试数 据看 GetRandomSequence2 的用时和 n 基本成正比，线性增长的，这个和理论上 的算法复杂度 O(n)也是一致的，另外两个算法则随着n 的增大，用时超过了线 性增长。在 1 百万时，我的算法比用hashtable 的算法要快 10 倍以上。 10000 100000 1000000 GetRandomSequence0 5 44 1075 GetRandomSequence1 11 1038 124205 GetRandomSequence2 1 7 82