## 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