Generate random number sequence without duplicates

Problem is: given a number, say 5;
Generate unique random number sequence between 1 and 5 (both included) like 3, 4, 5, 2, 1 or 1, 4, 5, 2, 3 etc.

Default approach will not ensure that sequences are unique. So, ensuring that the sequence is unique makes this problem interesting. 

I will be solving this problem in Java, using java.util.Random API. The approach is generic and hence can be employed in any programming language. 

Unique Random Sequence

As discussed, generating unique random sequence makes this problem interesting. This is because inbuilt API doesn't return unique sequence if you call nextInt(n) repeatedly. Below snippet confirms it.

  Random r = new Random();
for(int i=0; i<5; i++){
System.out.print(r.nextInt(5)+" ");
}
  //Produces : 4 4 0 0 2

Every time the nextInt method is called, the probability of getting a positive number less than 5 is equal. And hence number in the output could get repeated. On your system, you might get a different sequence but duplicates will still be there (run above snippet multiple time).

This can be solved by taking an array of given size and pre-populating it with unique numbers in the range. And then using the random number generator to shuffle these numbers. Above diagram illustrates its working.

           
                         r = rand.nextInt(5);

if r = 1; this means that value at pos(0) (or first element) should occupy the last position in the array.

So the first element will get swapped with the last element. Above diagram shows that the probability of occupying the last position is equal for all values. Once this is done, now all elements except the last one compete to occupy second last position.

So the generated random number could repeat, but the value at that position in the array is unique and it keeps on changing so the output is always going to be unique.

Java Implementation

Given below a Java method which generates a unique random number. 

 /**
  * Generate random number without duplicates in range 1,2..n Both 1 and n
  * are included
  * 
  * @param n
  *            up to number
  * @return List<Integer> randomly generated list
  */
 public List<Integer> generate(int n) {
  List<Integer> arr = new ArrayList<>(n);
  for (int i = 0; i < n; i++) {
   arr.add(i + 1);
  }
  System.out.println("input  :" + arr);

  Random rand = new Random();
  int r; // stores random number
  int tmp;

  //shuffle above input array
  for (int i = n; i > 0; i--) {
   r = rand.nextInt(i);
   
   tmp = arr.get(i - 1);
   arr.set(i - 1, arr.get(r));
   arr.set(r, tmp);
  }
  return arr;
 }

Output: [3, 4, 5, 2, 1]

---
keep coding !!!