Pseudo random number

Given a seed, and you will always get the next number, which is predictable. So that is reason why it is called pseudo random.

A simple algorithm is Linear congruential generator.


next random = (a * random + c) mod 2^32

The initial random is seed.

Java implementation

In next(bits) method:

nextseed = (oldseed * multiplier + addend) & mask;

here, multiplier is 0x5DEECE66DL, addend is 0xBL, mask is (1L « 48) - 1.

Shuffle

Shuffling is a procedure used to randomize a deck of playing cards to provide an element of chance in card games.

Fisher–Yates shuffle

implementation

For the unshuffled subarray, always select a random element swapping with the last one.

public void shuffle(int[] arr) {
   for(int len = arr.length; len > 1; --len) {
       int index = new Random().nextInt(len);
       int temp = arr[index];
       arr[index] = arr[len-1];
       arr[len-1] = temp;
   }
}

Please refer to Collections.shuffle(..). This algorithm has O(N) time complexity.

Practice

generate a 4-digit PIN code with no consecutive digits being the same

1232 is legal, but 1233 is illegal.

public static void main(String[] args) {
	List<String> list = new ArrayList<>();
	// generate all PINs 
	for(int i=0; i<= 9999; ++i) {
	  String pin = padding(i);
	  if(!pin.matches("\\d*(\\d)\\1\\d*")) {
	      list.add(pin);
	  }
	}
	
  // shuffle
  Collections.shuffle(list);
  
  // each time, select the last PIN
  int last = list.size() - 1;
  String pin = list.get(last);
  list.remove(last);
  System.out.println(pin);
}
	
private static String padding(int i) {
	int remaining = i;
	int d4 = remaining / 1000;
	remaining %= 1000;
	int d3 = remaining / 100;
	remaining %= 100;
	int d2 = remaining / 10;
	remaining %= 10;
	int d1 = remaining;
	
	return "" + d4 + d3 + d2 + d1;
}