Fisher–Yates shuffle (nonfiction): Difference between revisions
No edit summary |
No edit summary |
||
(2 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
The '''Fisher–Yates shuffle''' is an algorithm for generating a random permutation of a finite sequence—in plain terms, the algorithm shuffles the sequence. The algorithm effectively puts all the elements into a hat; it continually determines the next element by randomly drawing an element from the hat until no elements remain. The algorithm produces an unbiased permutation: every permutation is equally likely. The modern version of the algorithm is efficient: it takes time proportional to the number of items being shuffled and shuffles them in place. | The '''Fisher–Yates shuffle''' is an [[Algorithm (nonfiction)|algorithm]] for generating a random permutation of a finite sequence—in plain terms, the algorithm shuffles the sequence. The algorithm effectively puts all the elements into a hat; it continually determines the next element by randomly drawing an element from the hat until no elements remain. The algorithm produces an unbiased permutation: every permutation is equally likely. The modern version of the algorithm is efficient: it takes time proportional to the number of items being shuffled and shuffles them in place. | ||
The Fisher–Yates shuffle is named after Ronald Fisher and Frank Yates, who first described it | The Fisher–Yates shuffle is named after [[Ronald Fisher (nonfiction)|Ronald Fisher]] and [[Frank Yates (nonfiction)|Frank Yates]], who first described it. | ||
It is also known as the Knuth shuffle after Donald Knuth. | |||
A variant of the Fisher–Yates shuffle, known as Sattolo's algorithm, may be used to generate random cyclic permutations of length n instead of random permutations. | |||
== In the News == | == In the News == | ||
Line 11: | Line 15: | ||
* [[Crimes against mathematical constants]] | * [[Crimes against mathematical constants]] | ||
* [[Fisher–Yates shuffle]] | |||
* [[Gnomon algorithm]] | * [[Gnomon algorithm]] | ||
* [[Gnomon Chronicles]] | * [[Gnomon Chronicles]] | ||
Line 18: | Line 23: | ||
== Nonfiction cross-reference == | == Nonfiction cross-reference == | ||
* [[Algorithm (nonfiction)]] | |||
* [[Ronald Fisher (nonfiction)]] | |||
* [[Mathematics (nonfiction)]] | * [[Mathematics (nonfiction)]] | ||
* [[Frank Yates (nonfiction)]] | |||
External links: | External links: | ||
Line 25: | Line 33: | ||
[[Category:Nonfiction (nonfiction)]] | [[Category:Nonfiction (nonfiction)]] | ||
[[Category:Algorithms (nonfiction)]] | |||
[[Category:Mathematics (nonfiction)]] | [[Category:Mathematics (nonfiction)]] |
Latest revision as of 17:29, 23 March 2018
The Fisher–Yates shuffle is an algorithm for generating a random permutation of a finite sequence—in plain terms, the algorithm shuffles the sequence. The algorithm effectively puts all the elements into a hat; it continually determines the next element by randomly drawing an element from the hat until no elements remain. The algorithm produces an unbiased permutation: every permutation is equally likely. The modern version of the algorithm is efficient: it takes time proportional to the number of items being shuffled and shuffles them in place.
The Fisher–Yates shuffle is named after Ronald Fisher and Frank Yates, who first described it.
It is also known as the Knuth shuffle after Donald Knuth.
A variant of the Fisher–Yates shuffle, known as Sattolo's algorithm, may be used to generate random cyclic permutations of length n instead of random permutations.
In the News
Fiction cross-reference
- Crimes against mathematical constants
- Fisher–Yates shuffle
- Gnomon algorithm
- Gnomon Chronicles
- Mathematician
- Mathematics
Nonfiction cross-reference
External links:
- Fisher–Yates shuffle @ Wikipedia