Java生成不重复的随机数

Question

我想在Java中创建一组不带重复的随机数。

例如，我有一个数组用于存储从0到9999的10,000个随机整数。

这是我目前拥有的：

import java.util.Random;
public class Sort{

    public static void main(String[] args){

        int[] nums = new int[10000];

        Random randomGenerator = new Random();

        for (int i = 0; i < nums.length; ++i){
            nums[i] = randomGenerator.nextInt(10000);
        }
    }
}

但是上面的代码会创建重复项。我怎样才能确保随机数不会重复出现？

- Fernando Martinez

---

可能是在Java中生成唯一随机数的重复问题。 - JB Nizet

但是如果你移除重复的数字，那么它们就不再像随机数了。 - Joe Frambach

你想要数组中的所有10,000个数字以随机顺序排列，还是你想要10,000个随机数？因为你不能在0-9,999的范围内拥有10,000个随机数（那样它们就不再是随机的了）。 - GameDroids

是的，我只是不想让它们重复，这是最重要的事情。 - Fernando Martinez

你希望它不以“1 1 2”的方式重复吗？“1 2 1”是一个可接受的序列吗？ - user289086

Answer 1

Integer[] arr = {...};
Collections.shuffle(Arrays.asList(arr));

例如：

public static void main(String[] args) {
    Integer[] arr = new Integer[1000];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = i;
    }
    Collections.shuffle(Arrays.asList(arr));
    System.out.println(Arrays.toString(arr));

}

- Achintya Jha

---

洗牌很棒，但是首先你应该创建一个包含0到9999数字的数组，然后再进行洗牌。此外，洗牌的时间复杂度是多少？ - Martinsos

@Martinsos 我创建了一个数组并对其进行了洗牌。我不确定，但我认为洗牌的时间复杂度应该是O(n)。因为只是在数组内随机交换。 - Achintya Jha

Answer 2

一种简单的算法可以生成不重复的随机数，该算法可在书籍《编程珠玑》第127页中找到。

注意：生成的数组包含按顺序排列的数字！如果您想要它们以随机顺序排列，您需要使用Fisher-Yates洗牌算法或使用List并调用Collections.shuffle()来对数组进行洗牌。

这个算法的好处是您不需要创建一个包含所有可能数字的数组，并且运行时复杂度仍然是线性的O(n)。

public static int[] sampleRandomNumbersWithoutRepetition(int start, int end, int count) {
    Random rng = new Random();

    int[] result = new int[count];
    int cur = 0;
    int remaining = end - start;
    for (int i = start; i < end && count > 0; i++) {
        double probability = rng.nextDouble();
        if (probability < ((double) count) / (double) remaining) {
            count--;
            result[cur++] = i;
        }
        remaining--;
    }
    return result;
}

- the

---

注意：（关于您的“注意事项”部分）Collections.shuffle正在执行Fisher-Yates洗牌算法，因此这不是“二选一”的情况。 - Erwin Bolwidt

你是对的，Collections.shuffle 使用 Fisher-Yates 算法进行洗牌，但需要使用 List。Arrays.asList 需要数组类型为 Integer 而不是 int 才能正确转换，这样就不需要分配额外的内存。 自己编写 Fisher-Yates 洗牌算法可以避免转换，并且不需要额外的内存。 - the

只是想了解为什么需要 probability < ((double) count) / (double) remaining？为什么不从开头到结尾填充数组，然后随机打乱呢？ - brain storm

这个答案没有得到应有的赞誉。我一直在对结果进行直方图分析，以检查其随机性，到目前为止，结果的分布与预期一样均匀。例如，在sampleRandomNumbersWithoutRepetition(0, 100, 1)和Math.floor(Math.random()*100)之间没有明显的差异。 - Ricardo Marimon

@brainstorm 这种方法避免了构建整个数组。例如，如果您只想要范围在0..1000内的5个数字，这将避免创建995个您将要丢弃的东西的努力。 - Andy Turner

Answer 3

在Java 8中，如果您想要一个在范围（a，b）内非重复的N个随机整数列表，其中b是排除在外的，则可以使用类似以下代码的方式：

Random random = new Random();
List<Integer> randomNumbers = random.ints(a, b).distinct().limit(N).boxed().collect(Collectors.toList());

- Slawomir Domagala

---

这相当于 "random.ints(a, b).boxed().distinct().mapToInt(i -> i).limit(N).boxed().collect(...)"。效率不太高。而且，在底层它与Vaibhav Jain的实现是相同的，需要500500次迭代才能生成1000个元素。请花时间了解您使用的库。 - Torben

@Torben 实际上，在 Vaibhav Jain 的实现中，每次迭代找到适当的随机数的概率由(N-n+1)/N给出。其中 N 是所请求的总随机数，n 是当前迭代的数量。预期的迭代次数由 O(N log(N)) 给出，平均少于500500次。 参见 https://en.wikipedia.org/wiki/Coupon_collector%27s_problem - Slawomir Domagala

Answer 4

Achintya Jha在这里提出了正确的想法。不要考虑如何删除重复项，而是先删除创建重复项的能力。

如果您想坚持使用一个整数数组并希望随机化它们的顺序（手动操作非常简单），请按照以下步骤进行：

1.创建大小为n的数组。 2.循环遍历并将索引i处的每个值初始化为值i（或者如果您希望使用数字1到n而不是0到n-1，则为i + 1）。 3.最后，再次循环遍历数组，将每个值与随机索引处的值交换。

您的代码可以修改为以下内容：

import java.util.Random;

public class Sort
{
    // use a constant rather than having the "magic number" 10000 scattered about
    public static final int N = 10000;

    public static void main(String[] args)
    {
        //array to store N random integers (0 - N-1)
        int[] nums = new int[N];

        // initialize each value at index i to the value i 
        for (int i = 0; i < nums.length; ++i)
        {
            nums[i] = i;
        }

        Random randomGenerator = new Random();
        int randomIndex; // the randomly selected index each time through the loop
        int randomValue; // the value at nums[randomIndex] each time through the loop

        // randomize order of values
        for(int i = 0; i < nums.length; ++i)
        {
             // select a random index
             randomIndex = randomGenerator.nextInt(nums.length);

             // swap values
             randomValue = nums[randomIndex];
             nums[randomIndex] = nums[i];
             nums[i] = randomValue;
        }
    }
}

如果我是你的话，我可能会将这些代码块分解成单独的较小方法，而不是只有一个大型的主方法。

希望这可以帮助你。

- Benjamin Brumfield

Answer 5

如果您需要生成带有间隔的数字，可以像这样实现：

Integer[] arr = new Integer[((int) (Math.random() * (16 - 30) + 30))];
for (int i = 0; i < arr.length; i++) {
arr[i] = i;
}
Collections.shuffle(Arrays.asList(arr));
System.out.println(Arrays.toString(arr));`

结果： [1, 10, 2, 4, 9, 8, 7, 13, 18, 17, 5, 21, 12, 16, 23, 20, 6, 0, 22, 14, 24, 15, 3, 11, 19] 注意：

如果您不想让零离开，可以加上一个“if”条件。

- Marcus person

Answer 6

一个简单的流解决方案：

   new Random().ints(0, 10000)
        .distinct()
        .limit(10000)
        .forEach(System.out::println);

- olz

Answer 7

这个怎么样？

LinkedHashSet<Integer> test = new LinkedHashSet<Integer>();
Random random = new Random();
do{
    test.add(random.nextInt(1000) + 1);
}while(test.size() != 1000);

用户可以使用 for 循环迭代遍历 Set。

- Jitin Kodian

Answer 8

如果您正在使用JAVA 8或更高版本，可以按照以下方式使用流功能：

Stream.generate(() -> (new Random()).nextInt(10000)).distinct().limit(10000);

- Dhwanil Patel

Answer 9

public class RandomNum {
    public static void main(String[] args) {
        Random rn = new Random();
        HashSet<Integer> hSet = new HashSet<>();
        while(hSet.size() != 1000) {
            hSet.add(rn.nextInt(1000));
        }
        System.out.println(hSet);
    }
}

- K D

Answer 10

我们开始吧！

public static int getRandomInt(int lower, int upper) {
    if(lower > upper) return 0;
    if(lower == upper) return lower;
    int difference = upper - lower;
    int start = getRandomInt();
    
    //nonneg int in the range 0..difference - 1
    start = Math.abs(start) % (difference+1);
    
    start += lower;
    return start;
}

public static void main(String[] args){
    
    List<Integer> a= new ArrayList();
    
    int i;
    int c=0;
    for(;;) {
        c++;
        i= getRandomInt(100, 500000);
        if(!(a.contains(i))) {
            a.add(i);
            if (c == 10000) break;
            System.out.println(i);
        }
        
        
    }
    
    for(int rand : a) {
        System.out.println(rand);
    }
    
    
    
}

获取随机数 返回一个满足 lower <= x <= upper 的随机整数。如果 lower > upper，则返回 0。@param lower @param upper @return

在主方法中，我创建了一个列表，然后检查随机数是否存在于列表中，如果不存在，我将随机数添加到列表中。

这种方法非常慢但很直接。

- yome fisseha