FisherYatesShuffle

The Fisher-Yates shuffle, also known as the Knuth shuffle, is an algorithm for generating a random permutation of a finite sequence. In other words, it's a method for shuffling a list of items randomly so that each possible permutation of the items is equally likely. The algorithm was first described by Richard Durstenfeld in 1938 and later popularized by Donald Knuth.

The core idea of the Fisher-Yates shuffle is to iterate through the sequence from the last element down to the second element. In each iteration, a random element is chosen from the portion of the sequence that has not yet been shuffled (from the beginning of the sequence up to the current element) and swapped with the current element. Once an element is swapped, it is considered part of the shuffled portion.

A common implementation of the Fisher-Yates shuffle proceeds as follows: for i from n-1 down to 1 (where n is the length of the sequence), generate a random integer j such that 0 <= j <= i. Swap the element at index i with the element at index j. This process ensures that at each step, any of the remaining unshuffled elements has an equal probability of being placed in the current position. The result is a uniformly random permutation of the original sequence.