Generating Unique Random Numbers in Java

Generating Unique Random Numbers in Java

• Add each number in the range sequentially in a list structure.
• Shuffle it.
• Take the first 'n'.

Here is a simple implementation. This will print 3 unique random numbers from the range 1-10.

import java.util.ArrayList;
import java.util.Collections;

public class UniqueRandomNumbers {
    
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (int i=1; i<11; i++) list.add(i);
        Collections.shuffle(list);
        for (int i=0; i<3; i++) System.out.println(list.get(i));
    }
}

---

The first part of the fix with the original approach, as Mark Byers pointed out in an answer now deleted, is to use only a single Random instance.

That is what is causing the numbers to be identical. A Random instance is seeded by the current time in milliseconds. For a particular seed value, the 'random' instance will return the exact same sequence of pseudo random numbers.

Generating unique random numbers

Following are two possible approaches :-

Method 1 :-

1. Have all numbers in an array with size n.
2. select a number an index at random i = rand(0,size)
3. print arr[i]
4. swap arr[i] and arr[size-1]
5. size = size -1
6. repeat 1 to 5 till list is exhausted.

Time Complexity: O(N)

Space Complexity: O(N)

Method 2:-

1. Select a pool size of K.
2. generate K random integers.
3. show them as first k results.
4. Add them to a hashset.
5. Add all ak+1 for all previous integers in a pool.
6. Add 1 if it is not in hashset.
7. pick a integer r at random from pool and show it .
8. Add r+1 into pool if its not in hashset
9. Do 7 to 8 till pool is exhausted.

Time complexity: O(N)

Space complexity: O(K)

Pro & Cons :-

Method 1: Use this method for small integer ranges as it requires larger space but it is very fast and random.

Method 2: Use this method for larger ranges as it takes memory O(K) which is of your choice. The higher the k the higher is the randomness in the numbers generated. So you can achieve a nice trade off between space and randomness with maintaining good speed.

how to generate unique random numbers with a specific range

Solution 1:

I read Jon Skeet's comment, of course, this is the easiest solution:

List<Integer> list = new ArrayList<>();
for (int i = 0; i < 255; i++) {
     list.add(i);
}
//and here is the point. Java already have this implemented for you
Collections.shuffle(list);

Or in Java 8 declarative style:

List<Integer> list= IntStream.range(0, 255)
    .boxed()
    .collect(Collectors.toList());
Collections.shuffle(list);

or

List<Integer> list = new ArrayList<>();
IntStream.range(0, 255).forEach(list::add);
Collections.shuffle(list);

Solution 2 (picking up on your solution):

You need to generate number for each cell, and check if this number already exists:

 short [] array =new short[255];
 Random rand = new Random();

 for (int i=0; i<array.length; i++) {
     int random_integer = -1;

     //generate integer while it exists in the array
     while(exists(random_integer, array)) {
         random_integer = rand.nextInt(255);
     }

     array[i] = random_integer;
}

And now, let's check whether it exists:

public boolean exists(int number, int[] array) {
    if (number == -1)
        return true; 

    for (int i=0; i<array.length; i++) {
        if (number == array[i])
            return true;
    }
    return false;
}

Of course, you can use a hashmap for example, to speed up the exists() method, i.e. to lower the complexity from O(n) to O(1);

Generating Unique random numbers effectively in Java

You could create a set of random integers like this:

Set<Integer> set = new HashSet<Integer>();
Random rand = new Random();

while (set.size() < 10) {
    set.add(rand.nextInt((1000000)));
}

The idea is that the set data structure will remove duplicates.

What is optimal way to get four unique random number from 0-9?

You can use Collections.shuffle:

// generate a List that contains the numbers 0 to 9
List<Integer> digits = IntStream.range(0,10).boxed().collect(Collectors.toList());
// shuffle the List
Collections.shuffle (digits);
// take the first 4 elements of the List
int numbers[] = new int[4];
for(int i=0;i<4;i++){
    numbers[i] = digits.get(i);
}

How can I generate a unique random number each time when I run my application?

Do you want them to be truly random or truly unique? You can only have one of these.

If you want them to be truly random, then just randomly pick 9 digits from 0-9 and construct them into your number. There will be a small chance of a duplication, especially over larger numbers of iterations. It will be truly random, though.

If you want them to be truly unique, then you have to store every one in a database to ensure there are no duplicates. If you generate a duplicate, you'll need to regenerate or just increment the number and try again. If this is what you're looking for, it might be good to try just incrementing the value starting at one.

Generate unique random number on each call

Your method would indeed be ideal to create a large number of unique values, however if you are only creating a small number of unique values it can be more efficient to simply keep track of the used values to garantee uniqueness

import java.util.Collection;
import java.util.HashSet;
import java.util.Random;

public class UniqueRandom {

    static Random rnd=new Random();
    
    public static void main(String args[]){
        Collection<Integer> alreadyChosen = new HashSet<Integer>();
        for(int i=0;i<10;i++){
            System.out.println(getNextUniqueRandom (alreadyChosen));
        }
    }
    
    
    public static int getNextUniqueRandom(Collection<Integer> alreadyChosen){
        if (alreadyChosen.size()==90000){ //hardcoded 5 figure numbers, consider making a variable
             throw new RuntimeException("All 5 figure IDs used");
        }


        boolean unique=false;
        int value=0;
        while(unique==false){
            value=rnd.nextInt(90000)+10000;
            unique=!alreadyChosen.contains(value);
        }
        alreadyChosen.add(value);
        return value;
    }
    
}

This method is highly efficient when only a small proportion of the available range is required but becomes slower and slower as collisions become more common. The exact implementation you should choose is highly dependant upon how many values you need to get.

Notes to consider

• As already stated this will get very very slow as more values are
  chosen, should be made clear to end user, or even better; change algorithm after so many calls

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

}

---

Related Topics