[转] 高效的产生一组不重复的随机数

原文地址:
http://www.blogjava.net/lhulcn618/archive/2010/02/21/313522.html
需求描述:从 0 到 n 之间选 k 个不重复的数组成一个序列。
伪代码如下:

1
2
3
4
5
6
7
8
9
10
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]中存着呢,所以被选中的概率相等。
  最后附上 Java 实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void generateRandomNum(int count, int max) {
int temp = 0;
int[] seed = new int[max];
for (int i = 0; i < max; i++) {
seed[i] = i + 1;
}
int[] ranArr = new int[count];
Random ran = new Random();
for (int i = 0; i < count; i++) {
int j = ran.nextInt(max) % (max+ 1);
temp = seed[i];
seed[i] = seed[j];
seed[j] = temp;
ranArr[i] = seed[i];
}
System.out.println(Arrays.toString(ranArr));
}

PS: 后来我发现 Java 的 Collections.shuffle() 方法的实现,也是采用的这个算法。看来这个算法是相当的经典啊!

坚持原创及高品质技术分享,您的支持将鼓励我继续创作!