Published by Dimitris Kougioumtzis · Updated
Swap the last unfixed position with a uniformly selected position in its remaining prefix. Seeded Park-Miller draws use rejection to avoid modulo bias.
Move the boundary of the unfixed prefix from right to left. Draw an index uniformly from that prefix and swap it into the boundary position, fixing one position at every step.
When to use Seeded Fisher-Yates shuffle
Reproducible shuffling for teaching and deterministic simulations.
Choosing an alternative
Sorting by random comparison keys does not implement a reliable uniform shuffle. Fisher-Yates makes one bounded choice for each unfixed position.
Worked example: input and state changes
Example input
1,2,3,4,5,6,7,8 | 17
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Fix positions from right to left.
State at this checkpoint
{ "values": [ 1, 2, 3, 4, 5, 6, 7, 8 ], "active": [], "result": 17, "output": [ 1, 2, 3, 4, 5, 6, 7, 8 ] }Step 2: Swap positions 6 and 4.
State at this checkpoint
{ "values": [ 1, 2, 3, 4, 8, 6, 5, 7 ], "active": [ 6, 4 ], "result": 507111939, "output": [ 1, 2, 3, 4, 8, 6, 5, 7 ] }Step 4: Swap positions 4 and 1.
State at this checkpoint
{ "values": [ 6, 8, 3, 4, 2, 1, 5, 7 ], "active": [ 4, 1 ], "result": 1711656657, "output": [ 6, 8, 3, 4, 2, 1, 5, 7 ] }Step 6: Swap positions 2 and 0.
State at this checkpoint
{ "values": [ 4, 8, 6, 3, 2, 1, 5, 7 ], "active": [ 2, 0 ], "result": 1551140683, "output": [ 4, 8, 6, 3, 2, 1, 5, 7 ] }Step 8: Shuffled; final PRNG state 1717468248.
State at this checkpoint
{ "values": [ 4, 8, 6, 3, 2, 1, 5, 7 ], "active": [], "result": 1717468248, "output": [ 4, 8, 6, 3, 2, 1, 5, 7 ] }
Expected final state
Shuffled; final PRNG state 1717468248.
Complexity and input bounds
Family: Randomized. Time complexity: O(n) expected time.
Implementation detail: At most 24 values are shuffled in place. Park-Miller seeds range from one through 2147483646; downloads return the final state. Portable integer versions use Schrage decomposition to avoid signed overflow. The same seed and input reproduce every swap across all nine languages.
Space complexity: O(1) auxiliary shuffle storage, excluding recorded frames.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
1..24 values 0..99 | seed 1..2147483646. The same seed reproduces the same swaps.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Include the current boundary position among possible choices. Direct modulo reduction can bias bounded draws, so reject the excess tail of the generator range. Identical values still represent separate positions.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 | // Fisher-Yates in-place shuffle, n 0..24 values 0..99, seed 1..2147483646. Returns final Park-Miller state, or -1 for invalid seed before modifying input. PRNG state advances as 16807*state modulo 2147483647; portable versions use Schrage decomposition to avoid signed 32-bit overflow. Draw state-1 uniformly from 0..2147483645 and reject values outside the largest prefix divisible by the requested bound, then take modulo. Empty/singleton input consumes no draws. O(n) expected time, O(1) scratch. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(a, n, seed) { if (seed < 1 || seed > 2147483646) { return -1; } let state = seed; let bound = 0; let choice = 0; let accepted = 0; let value = 0; let limit = 0; let temp = 0; for (let i = n-1; i > 0; i--) { bound = i+1; limit = 2147483646-(2147483646%bound); accepted = 0; while (accepted == 0) { state = 16807*(state%127773)-2836*(Math.floor(state / 127773)); if (state <= 0) { state += 2147483647; } value = state-1; if (value < limit) { choice = value%bound; accepted = 1; } } temp = a[i]; a[i] = a[choice]; a[choice] = temp; } return state; } |
Source
Knuth is a reference for shuffling, not an asserted original Fisher-Yates paper. Park-Miller supplies the reproducible generator, not the invention of the shuffle.
- The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd edition)
Donald E. Knuth (1997). Reference book. - Random Number Generators: Good Ones Are Hard to Find
Stephen K. Park; Keith W. Miller (1988). Primary research paper.