生成数组中的随机数

Question

可能的重复：
O(1) 内的唯一随机数？

我是 Java 新手。我想从给定的集合中生成一组随机数，并且这些数字也不能重复。例如，可能的数字是[0,1,2,3]，我想获得存储在数组中的三个随机唯一数字。前任。 [0,2,1]、[2,3,1]、[0,3,2] 等。

Answer 1

你需要费舍尔-耶茨洗牌。

这是一个非常高效的“从 m 中选择 n”解决方案，它为您提供值的子集，重复的可能性为零（并且没有不必要的预先排序）。执行此操作的伪代码如下：

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]

只需从池中选择一个随机数（基于当前池大小），将其替换为该池中的顶部数字，然后减小池的大小，您就可以进行洗牌，而无需预先担心大量的交换。

如果数字很大，这一点很重要，因为它不会引入不必要的启动延迟。

例如，检查以下基准检查，从 10 中选择 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

您可以看到池随着您的使用而减少，并且因为您总是用未使用的替换旧的，所以您永远不会重复。

---

下面是一个小 Java 程序，它展示了这一点：

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());
    }
}

输出（对于一次特定的运行）：

3
5
1
0
6
4
9
2
8
7
-1

-1 只是为了向您展示当您耗尽列表时会发生什么。由于您已明确声明不希望出现重复项，因此它会返回一个哨兵值。您还可以选择其他选项，例如引发异常或仅重新启动池。