Java generating non-repeating random numbers

Question

I want to create a set of random numbers without duplicates in Java.

For example I have an array to store 10,000 random integers from 0 to 9999.

Here is what I have so far:

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

But the above code creates duplicates. How can I make sure the random numbers do not repeat?

Answer 1

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

For example:

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

Answer 2

A simple algorithm that gives you random numbers without duplicates can be found in the book Programming Pearls p. 127.

Attention: The resulting array contains the numbers in order! If you want them in random order, you have to shuffle the array, either with Fisher–Yates shuffle or by using a List and call Collections.shuffle().

The benefit of this algorithm is that you do not need to create an array with all the possible numbers and the runtime complexity is still linear 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; }