# Fisher-Yates shuffle (Forth)

### From LiteratePrograms

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:

- Let
be the list,**A**be its length,**N**–**A**_{1}be its elements. Let**A**_{N}be**i**.**N** - Let
be random between 1 and**r**(inclusive).**i** - If
is not equal to**i**, swap**r**and**A**_{r}.**A**_{i} - Decrease
by one.**i** - Repeat steps 2 through 4 until
equals 1.**i**

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 !

Download code |