Informática geek, matemáticas, pensamiento crítico y alguna otra cosa de vez en cuando.

2013-08-07

Inside-out Fisher-Yates algorithm

The inside-out Fisher-Yates shuffling algorithm looks like this:

  outputlength = 0
  while there are input elements:
    r := random number between 0 and outputlength inclusive
    if r <> outputlength:
      output[outputlength] := output[r]
    output[r] := next input element
    outputlength := outputlength + 1

Here's an animation that shows it in action:

For artistic purposes, the animation shows how the "pushed" element goes to the end of the array after the position where it was originally is replaced by the incoming element. In the algorithm, that step actually precedes the replacement.

No comments: