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 A be the list, N be its length, A1–AN be its elements. Let i be N.
- Let r be random between 1 and i (inclusive).
- If i is not equal to r, swap Ar and Ai.
- Decrease i by one.
- 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 !
| Download code |