Thursday, 20 July 2017

Algorithms | Generate n unique Random numbers

 Fisher–Yates shuffle Algorithm works in O(1) time complexity to generate the random number. The idea is to start from the last element, swap it with a randomly selected element from the whole array (including last). Now consider the array from 0 to n-2 (size reduced by 1), and repeat the process till we hit the first element.

RandomGenerator.java
package com.algorithmforum.rand;
import java.util.Random;
public class RandomGenerator {

     private static int[] array = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

     private static int maxIdx = array.length-1;

     /** This function to generate a random number for every new request. */
     private static int genRand() {
           /*
            * Start from the last element and swap one by one.
            * We don't need to run for the first element that's why i> 0
            */

           /** Pick a random index from 0 to i.*/
           Random rand = new Random();
           int randIdx = rand.nextInt(50);
           int j = randIdx % (maxIdx+1);

           /** Swap array[i] with the element at random index. */
           swap(maxIdx, j);
          
           return array[maxIdx--];
     }

     /** A utility function to swap to integers. **/
     private static void swap (int i, int j) {
           int temp = array[i];
           array[i] = array[j];
           array[j] = temp;
     }

     /** Driver method. */
     public static void main(String[] args) {
           for (int i = 0; i <=10; i++) {
                int random = RandomGenerator.genRand();
                System.out.println("Random number "+i+": "+ random);
           }
     }
}

Output:
Random number 0: 7
Random number 1: 8
Random number 2: 10
Random number 3: 6
Random number 4: 5
Random number 5: 9
Random number 6: 0
Random number 7: 3
Random number 8: 2
Random number 9: 4
Random number 10: 1


No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...