# Fisher-Yates shuffle (Forth)

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.

```<<shuffle.fs>>=
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 !
```