Fisher-Yates Shuffle

The Fisher-Yates shuffle is an algorithm for shuffling a finite sequence, taking a list of all the sequence's elements and continually drawing the next element of the shuffled output at random from the elements remaining. It produces an unbiased permutation, meaning every possible permutation is equally likely, and the modern version runs in time proportional to the number of items being shuffled and rearranges them in place. It is named after Ronald Fisher and Frank Yates, who first described it, and is also known as the Knuth shuffle after Donald Knuth; a variant called Sattolo's algorithm generates random cyclic permutations instead of random permutations.