# 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;
}
``````