生成数组中的随机数 [英] Generate Random Numbers in Array
问题描述
可能的重复:
O(1) 中的唯一随机数?
我是 Java 新手.我想从给定的集合中生成一组随机数，并且这些数字也不能重复.例如，可能的数字是 [0,1,2,3]，我想将三个随机的唯一数字存储在一个数组中.前任.[0,2,1], [2,3,1], [0,3,2] 等
I am new in Java. I want to generate a set of random numbers from a given set and the numbers must also not repeat. For example, the possible numbers are [0,1,2,3], I want to get three random unique numbers stored in an Array. Ex. [0,2,1], [2,3,1], [0,3,2] etc.
推荐答案
你需要一个 Fisher-Yates shuffle.
You need a Fisher-Yates shuffle.
这是一个非常有效的从 m 中选择 n"的解决方案，它为您提供一个值的子集，重复的可能性零(并且没有不必要的预先排序).执行此操作的伪代码如下:
This is a very efficient "select n from m" solution that gives you a subset of your values with zero possibility of duplicates (and no unnecessary up-front sorting). Pseudo-code to do this follows:
dim n[N] // gives n[0] through n[N-1]
for each i in 0..N-1:
n[i] = i // initialise them to their indexes
nsize = N // starting pool size
do N times:
i = rnd(nsize) // give a number between 0 and nsize-1
print n[i]
nsize = nsize - 1 // these two lines effectively remove the used number
n[i] = n[nsize]
通过简单地从池中选择一个随机数(基于当前池大小)，将其替换为该池中的顶部数字，然后减小池的大小，您就可以进行洗牌而不必担心大预先交换的次数.
By simply selecting a random number from the pool (based on the current pool size), replacing it with the top number from that pool, then reducing the size of the pool, you get a shuffle without having to worry about a large number of swaps up front.
如果数量很大，这很重要，因为它不会引入不必要的启动延迟.
This is important if the number is high in that it doesn't introduce an unnecessary startup delay.
例如，检查以下基准检查，选择 10-from-10:
For example, examine the following bench-check, choosing 10-from-10:
<------ n[] ------>
0 1 2 3 4 5 6 7 8 9 nsize rnd(nsize) output
------------------- ----- ---------- ------
0 1 2 3 4 5 6 7 8 9 10 4 4
0 1 2 3 9 5 6 7 8 9 7 7
0 1 2 3 9 5 6 8 8 2 2
0 1 8 3 9 5 6 7 6 6
0 1 8 3 9 5 6 0 0
5 1 8 3 9 5 2 8
5 1 9 3 4 1 1
5 3 9 3 0 5
9 3 2 1 3
9 1 0 9
您可以看到池随着使用而减少，并且因为您总是用未使用的替换已使用的池，所以您永远不会重复.
You can see the pool reducing as you go and, because you're always replacing the used one with an unused one, you'll never have a repeat.
这是一个小 Java 程序，它显示了这一点:
Here's a little Java program that shows this in action:
import java.util.Random;
public class testprog {
private int[] pool; // The pool of numbers.
private int size; // The current "size".
private Random rnd; // A random number generator.
// Constructor: just initilise the pool.
public testprog (int sz) {
pool = new int[sz];
size = sz;
rnd = new Random();
for (int i = 0; i < size; i++) pool[i] = i;
}
// Get next random number in pool (or -1 if exhausted).
public int next() {
if (size < 1) return -1;
int idx = rnd.nextInt(size--);
int rval = pool[idx];
pool[idx] = pool[size];
return rval;
}
// Test program for the pool.
public static void main(String[] args) {
testprog tp = new testprog (10);
for (int i = 0; i < 11; i++) System.out.println (tp.next());
}
}
输出是(对于一次特定的运行):
The output is (for one particular run):
3
5
1
0
6
4
9
2
8
7
-1
-1 只是为了向您展示当您用尽列表时会发生什么.由于您已明确声明您不想要重复项，因此它返回一个标记值.您还可以选择其他选项，例如抛出异常或重新启动池.
The -1 is there just to show you what happens when you exhaust the list. Since you've explicitly stated you don't want duplicates, it returns a sentinel value. You could also choose other options such as throwing an exception or just restarting the pool.
这篇关于生成数组中的随机数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
