Category:Fisher-Yates shuffle

From LiteratePrograms
Jump to: navigation, search

The Fisher-Yates shuffle is the most used algorithm for shuffling lists or arrays. In its original wording, you should get a random element from the original list into an accumulator until the original list is empty. In practice, a more convoluted wording is commonly used, which shuffles a list in-place:

  1. Let A be the list, N be its length, A1AN be its elements. Let i be N.
  2. Let r be random between 1 and i (inclusive).
  3. If i is not equal to r, swap Ar and Ai.
  4. Decrease i by one.
  5. Repeat steps 2 through 4 until i equals 1.

The algorithm complexity is O(n).


Pages in category "Fisher-Yates shuffle"

This category contains only the following page.