Shuffling algorithms and randomization to improve algorithm‘s runtime.
Shuffling cards is an essential part of every card game. There are many techniques for shuffling cards but overhand and riffle are the most popular ones.
In this shuffle a set of cards are transferred from bottom of the deck to the top of the deck and the same process gets executed recursively.
A deck of cards is essentially a fixed sized array of length 52. Overhand shuffle puts set of cards from the end of the array to the beginning of array. This process gets repeated to get a good shuffle.
This involves cutting the deck into 2 halves so we get two set of cards and riffle them such that at the end both half gets interleaved.
There are shuffling algorithms in existence that runs faster and gives consistent results. These algorithms relies on randomization to generate a unique random number on each iteration.
As per wikipedia
If a computer has access to purely random numbers, it is capable of generating a “perfect shuffle”.
Fisher-Yates shuffle is one such algorithm for achieving a perfect shuffle using random number generator. Algorithm is named after Ronald Fisher and Frank Yates who first described this algorithm in their book in 1938. Later Donal Knuth and Richard Durstenfeld introduced improved version of the algorithm in 1964.
Unlike swapping items at two different index, algorithm generates a random number k between range of the elements inside an array. Every iteration updates the last element in the range thus random generator works on new range on every iteration and generates a unique number every time.
Above algorithm works in linear time and faster than riffle shuffle. Putting some timing around both shuffle algorithm for an array of 100 integers produces below result.
************** Riffle Shuffle ***************
Time Taken is-: 45298827
*************** Knuth Shuffle **************
Time Taken is-: 1325950
Programming languages use similar algorithm in their inbuilt implementation of shuffle method. Java’s implementation of shuffle method could be used by invoking
To shuffle a linked list which doesn’t not allow access of object by their index, Java converts it back to array first so to have random access, shuffles it and converts it back to list.
Can randomization improve runtime of an algorithm.
A good shuffling algorithm has a function which generates a unique random number consistently. Quick sort which gives quadratic time performance on sorted array can generate consistent O(nlogn) result by randomizing sorted array first and then fed it into quick sort algorithm.
There are two different types of randomization algorithms namely Las Vegas and Monte Carlo algorithms. IMHO, one can’t get a better name than Las Vegas for a shuffling algorithm :)
Las Vegas algorithm guarantees to give result in expense of the time complexity whereas Monte Carlo compromises guarantee of result by exiting early if it doesn’t find the desired output. If we have to search an item inside an array Las Vegas algorithm will execute until it finds the expected item whereas Monte Carlo will execute for couple of cycles and stops if it doesn’t find the item. Rabin Karp algorithm for string searching uses Las Vegas algorithm to find all matching sub-string inside input string.
Randomized algorithms are useful in applications that requires good results consistently irrespective of input to the algorithms. Software in rockets, satellites, airplane, cryptography utilizes randomization to get high probability of good result on algorithm
Fisher-Yates shuffle - Wikipedia
The Fisher-Yates shuffle is an algorithm for generating a random permutation of a finite sequence-in plain terms, the…
Randomized Algorithms | Set 2 (Classification and Applications) - GeeksforGeeks
We strongly recommend to refer below post as a prerequisite of this. Randomized Algorithms | Set 1 (Introduction and…
Images are taken from google.
There is so much to learn and write about shuffling algorithms and randomization. In my next post, we’ll sort back cards after shuffling them in here using inbuilt sort function in language.
Stay tuned :)