Saturday, September 6, 2014

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. 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 nextInt method is called, the probability of getting 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 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 array.
So first element will get swapped with last element. Above diagram shows that probability of occupying last position is equal for all values. Once this is done, now all elements except 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 output is always going to be unique.

Java Implementation

Given below a Java method which generates 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 !!!

1 comment:

  1. I wish to generate a set of random numbers but the same set of numbers should be displayed when executing the program each time but without duplicates. Please help

    ReplyDelete