Subsequent editions of Knuth's The Art of Computer Programming mention Fisher and Yates' contribution. Neither Durstenfeld's article nor Knuth's first edition of The Art of Computer Programming acknowledged the work of Fisher and Yates they may not have been aware of it. Knuth in The Art of Computer Programming as "Algorithm P (Shuffling)".
The modern version of the Fisher–Yates shuffle, designed for computer use, was introduced by Richard Durstenfeld in 1964 and popularized by Donald E. They also suggested the possibility of using a simpler method - picking random numbers from one to N and discarding any duplicates-to generate the first half of the permutation, and only applying the more complex algorithm to the remaining half, where picking a duplicate number would otherwise become frustratingly common.
RANDOM LIST GENERATOR NO REPEATS HOW TO
Fisher and Yates took care to describe how to obtain such random numbers in any desired range from the supplied tables in a manner which avoids any bias. Provided that the random numbers picked in step 2 above are truly random and unbiased, so will be the resulting permutation.
The sequence of numbers written down in step 3 is now a random permutation of the original numbers. Repeat from step 2 until all the numbers have been struck out. Counting from the low end, strike out the kth number not yet struck out, and write it down at the end of a separate list. Pick a random number k between one and the number of unstruck numbers remaining (inclusive). Write down the numbers from 1 through N. The basic method given for generating a random permutation of the numbers 1 through N goes as follows: Their description of the algorithm used pencil and paper a table of random numbers provided the randomness. The Fisher–Yates shuffle, in its original form, was described in 1938 by Ronald Fisher and Frank Yates in their book Statistical tables for biological, agricultural and medical research. 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.įisher and Yates' original method The Fisher–Yates shuffle is named after Ronald Fisher and Frank Yates, who first described it, and is also known as the Knuth shuffle after Donald Knuth. The modern version of the algorithm takes time proportional to the number of items being shuffled and shuffles them in place. The algorithm produces an unbiased permutation: every permutation is equally likely. The algorithm takes a list of all the elements of the sequence, and continually determines the next element in the shuffled sequence by randomly drawing an element from the list until no elements remain. 
The Fisher–Yates shuffle is an algorithm for shuffling a finite sequence. Example of shuffling five letters using Durstenfeld's in-place version of the Fisher–Yates shuffle
0 kommentar(er)
