在数组中生成随机数

Z时代
2024-01-10
分类：问答

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

回答：

您需要一个Fisher-Yates混洗。

这是一个非常有效的“从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());
    }
}