The Fisher-Yates shuffle is backward
a day ago
- #algorithm
- #shuffling
- #Fisher-Yates
- The Fisher-Yates shuffle is the standard algorithm for shuffling a list to ensure all permutations are equally likely.
- A forward variant of the Fisher-Yates shuffle is proposed, which simplifies the loop structure by iterating from the start to the end of the list.
- The forward shuffle maintains a loop invariant where each sublist up to the current index is a uniformly random permutation of the original sublist.
- The forward shuffle is equivalent to the 'inside-out' version of Fisher-Yates, typically used for external sources of unknown length.
- The standard backward Fisher-Yates shuffle is implemented in major programming languages like Go, CPython, and OpenJDK.
- The backward shuffle may have advantages in memory or cache efficiency as the 'finished' zone grows and the 'hot' zone shrinks.
- The forward shuffle can be adapted for reservoir sampling, allowing efficient sampling from a stream of unknown length.