Java generating non-repeating random numbers

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

}

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

In Java 8, if you want to have a list of non-repeating N random integers in range (a, b), where b is exclusive, you can use something like this:

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

Achintya Jha has the right idea here. Instead of thinking about how to remove duplicates, you remove the ability for duplicates to be created in the first place.

If you want to stick with an array of ints and want to randomize their order (manually, which is quite simple) follow these steps.

create array of size n.
loop through and initialize each value at index i to the value i (or i+1 if you wish to have the numbers 1 to n rather than 0 to n-1).
finally, loop through the array again swapping each value for a value at a random index.

Your code could be modified to look like this:

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

And if I were you I would likely break each of these blocks into separate, smaller methods rather than having one large main method.

Hope this helps.

If you need generate numbers with intervals, it can be just like that:

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

The result:

[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]

Note:

If you need that the zero does not leave you could put an "if"

Java generating non-repeating random numbers

Related

Recent Posts