The Fisher-Yates Shuffle Is Backward
Key topics
The Fisher-Yates shuffle algorithm has sparked a lively debate over its "forward" and "backward" implementations, with commenters sharing their personal preferences and insights into the algorithm's intuitiveness. While some, like amluto, find the backward version more intuitive, others, like dunham, interpret the forward version as randomly selecting a card and putting it at the bottom of a new pile. Notably, shiandow and dooglius discuss the algorithm's adaptability for sampling k elements, with shiandow suggesting that ignoring elements beyond the first k still yields a uniform distribution. As the discussion reveals, both versions have their merits, and the "right" approach ultimately depends on individual perspectives.
Snapshot generated from the HN discussion
Discussion Activity
Active discussionFirst comment
19h
Peak period
12
120-132h
Avg / period
7.3
Based on 22 loaded comments
Key moments
- 01Story posted
Dec 20, 2025 at 9:17 AM EST
21 days ago
Step 01 - 02First comment
Dec 21, 2025 at 4:32 AM EST
19h after posting
Step 02 - 03Peak activity
12 comments in 120-132h
Hottest window of the conversation
Step 03 - 04Latest activity
Dec 25, 2025 at 6:47 PM EST
15 days ago
Step 04
Generating AI Summary...
Analyzing up to 500 comments to identify key contributors and discussion patterns
Want the full context?
Jump to the original sources
Read the primary article or dive into the live Hacker News thread when you're ready.
I suppose one of the benefits of having a poor memory is that one sometimes improves things in the course of rederiving them from an imperfect recollection.
Maybe it's because it's so easy to prove to yourself that Fisher-Yates generates every possible combination with the same probability[1], and so forwards or backwards just doesn't register as relevant.
[1]This of course makes the a hefty assumption about the source of random numbers which is not true in the vast majority of cases where the algorithm is put into practice as PRNGs are typically what's used. For example if you use a PRNG with a 64 bit seed then you cannot possibly reach the vast majority of states for a 52 card deck; you need 226 bits of state for that to even be possible. And of course even if you are shuffling with fewer combinations than the PRNG state can represent, you will always have some (extremely slight) bias if the state does not express an integer multiple of the number of permutations of your array size.
You could also call the last version the online version, as it will ensure the partial list is random at any point in time (and can be used for inputs with indeterminate length, or to extend a random list with new elements, sample k elements etc.)
Not too sure if the enumerate is necessary. I usually dislike using it just to have an index to play around with. A similar way of doing the same thing is:
Which makes the intention a bit clearer. You could even avoid the swap entirely but you would need to handle the case where i is at the end of the list separately.Not quite sure what you have in mind here, but you need reservoir sampling for this in order to make the selection uniformly random (which I assume is what's desired)
Suppose I want to uniformly randomly shuffle a deck of cards in a single pass. I stick the deck on the table and call it the non-shuffled pile. My goal is to move the deck, one card at a time, into the shuffled pile. First I need to select a card, uniformly at random, to be the bottom card of the new pile, and I move it over. Then I select another card, uniformly at random from the still non-shuffled cards, and put it on top of the bottom shuffled card. I repeat this until I’ve moved all the cards, so that each card in the shuffled pile is a uniform random selection from all of the cards it could have been. And that’s it.
One can think of this as random selection, whereas the “forward” version is like random insertion of a not-random card into a shuffled pile. And for whatever reason I tend to think of the selection version first.
both seem intuitive from individual perspectives
`mirror_shuffle` is the (GROUP) CONJUGATE of `fisher_yates_shuffle` by the cyclic permutation (n-1,n-2,...,1,0). In group theory, CONJUGATEs are like changes of coordinates. In this case, they reverse the index labels.
For me, the reason for reaching for the “backwards” version first is that it wasn’t as clear to me that the “forward” version makes a uniform distribution.
Even after reading the article.
I appreciated the comment here about inserting a card at a random location, but that also isn’t quite right, because you swap cards not insert. Nevertheless, that did it for me.