Fisher-Yates shuffle (Forth)

From LiteratePrograms

Jump to: navigation, search
Other implementations: Erlang | Forth | Haskell

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).

This algorithm uses a standard count up loop instead of the specified count down loop. This necessitates selecting a random element from those above i instead of those below i.

include random.fs      \ for random ( n -- 0..n-1 )
: shuffle { array size -- }
  size 1- 0 do
    select random item above i
    swap with i-th item
  loop ;
<<select random item above i>>=
    size i - random  i + cells array +
<<swap with i-th item>>=
    array i cells + @  over @
    array i cells + !  swap !
Download code
Personal tools