5 ms·
Show HN: A visual explanation of Fisher–Yates shuffle
- joechapman 15y agoIn your last example you could do; [array[m], array[i]] = [array[i], array[m]] And forget about t entirely.
- iamwil 15y agoI have a question. Why does the shuffled deck have the cards criss-crossed with its neighbors? I'm not sure what it's suppose to represent.
- iamwil 15y agoNevermind. I just answered my own question. It's a result of the original deck being fanned visually. So when he reshuffles the deck, the cards are still orientated in the same direction as they were in the original deck, so you get the visual side-effect of having cross-crossed cards. So you can tell approximately which side of the deck the card was from originally. And by visual estimation, a properly shuffled deck should have a combination of cards orientated in all different directions.
- CountHackulus 15y agoWhich if you look at the sorting visualization links at the bottom, is actually a really effective way of showing when things are very out of order, or close to in order.
- mbostock 15y agoThe angle of the lines encodes the value of the card. The lowest-value cards lean left, and the highest-value cards lean right. The in-order deck, therefore, neatly fans from left-to-right. In the shuffled deck the values are in random order, so the lines often cross.
- manifold 15y agoGreat article. This is probably a question for the statisticians: Would repeatedly sampling from a uniform distribution mean that on average the next card chosen will come from the middle of the remaining pack (as repeatedly sampling from a uniform distribution gives a normal distribution), or does the decreasing sample size somehow cancel that effect out? Then at the same time the algorithm is moving cards from the end towards the middle. Intuitively it feels like the shuffle ought to be biased towards selecting the middle-end of the pack first, but wikipedia indicates it's unbiased. Any help with getting further intuition?
- skimbrel 15y agoThe key here is that you aren't sampling the same uniform distribution each time. You shrink the sample space by one each time you remove a card and append it to the end.
- klochner 15y agoRepeatedly sampling from a uniform distribution gives a uniform distribution - uniform means the probability is the same for all cards.
- manifold 15y agoYes, but the average value of the sampled values will tend towards a Normal distribution by the central limit theorem, and I'm probably misapplying it by wondering whether the next sample tends to be from nearer the middle. I think skimbrel is right that as the sample being drawn from is decreasing each time the CLT will be invalidated anyway.
- klochner 15y agoSorry to be blunt, but you're confused. The average of the sampled values will be normally distributed, but the values themselves will be uniform. If you sample every number once from [0,100], the average is 50, but that doesn't imply that the distribution of the sampled elements is normal - it's uniform. His question of whether "on average, does the next card come from the middle" (which it doesn't) isn't the same as "is the mean of the next sampled card in the middle" (which it is). The language was a little misleading - he said "on average" when he intended "most frequently".
- lnanek 15y agoThis is a pretty common way to use arrays, at least in game programming on earlier versions of Android where you couldn't garbage collect during a frame due to the delays. You'd often have big pre-allocated arrays with a marker for how much is currently used. That or object pools when you needed someone more than arrays.
- substack 15y agoThanks for posting this! I just updating my own silly shuffle module (https://github.com/substack/node-deck https://github.com/substack/node-deck) to work using the last in-place algorithm for uniform shuffling and I saw a huge speedup.
- benmathes 15y agoPet Peeve of mine with math: Fisher and Yates have come up with something interesting here, yes. But like most mathematical theorems named after someone, attaching their names to it doesn't help understanding of what it does at all. I don't name my functions benmathes_foo().
- teej 15y agoAnd quicksort doesn't tell me anything about the algorithm either. It's just a name. Things need to be distinctly identified in a set. That's really the only purpose of a name anyway.
- philh 15y agoAttaching the name doesn't even tell you who came up with it, in general. Unfortunately, it can be hard to generate names which are a) descriptive, b) distinct, c) short. But we've done pretty okay with sorting algorithms, and I definitely feel that more is possible.
- burgerbrain 15y agoTo be fair, the wikipedia page for the algorithm is called "Fisher–Yates shuffle". This is in my experience a common way to call an algorithm. I can't think of a better way to do it.
- benmathes 15y agoAfter putting a few seconds of thought into it, "In place shuffle" explains what it does better than "Fisher-Yates shuffle". I'm not complaining about Fisher or Yates, who are just following the example their/our research community uses.
- gerggerg 15y agoBeautiful. I love the visual demonstrations of the less efficient methods as well. This is a great learning tool for a super common programming problem. One general comment/question. Code like this trips me up: t = array[--m]; Well I don't know if it trips me up so much as it makes me think too much about syntax especially when the focus is on the algorithm itself. When writing educational code I find the following more effective: m -= 1; t = array[m]; Anyone else have any thoughts?
- barik 15y agoI agree, if the intent is for pedagogical purposes (as in this case), the use of pre-increment and post-increment operators should probably be avoided. A good rule of thumb is that if you find yourself having to say "and" too many times when describing a single line -- then it's probably doing too much. In fact, I was actually thinking more of this example: i = Math.floor(Math.random() * n--); when I stumbled across your comment. Otherwise, that's a minor criticism and it's a good page overall. In fact, it was one of the interview questions I was asked when I interviewed at Microsoft a long time ago. At the time, I didn't realize the algorithm actually had a name.
- Jagat 15y agoMost of the mainstream languages support these operators and programmers are encouraged to use these operators since they make the code much more elegant and readable. Even an average programmer would be able to understand the nuances of post/pre increment/decrement operators.
- gerggerg 15y agoI definitely understand it. It's not a matter of understanding the syntax. It's a matter of teaching people most effectively. Here's a comparison of the spoken explanation of the code: 't' equals the value of 'array' at index 'm' minus 1 and 'm' equals itself minus 1. vs 'm' equals itself minus 1. 't' equals the value of 'array' at index 'm'. To me one of those seems more concise for writing production code, and the other more useful for teaching algorithms.
- mef 15y agoGreat post, and extra points for visualizations that work on the iPhone.
- justincormack 15y agoIt uses d3.js, which pretty much requires a modern browser with SVG. I suspect you will find it doesn't work on IE8.
- josephmoniz 15y agoThe final method uses a really common programming idiom for optimizing the removal of elements in a std::vector known as "swap and pop". Swap and pop works by taking advantage of the facts that the most efficient element you can remove from an array/vector is the last one by `pop`ing it off and that the preserved order of the given set isn't important. // swap and pop in C++11 int offset = 2; // remove the second element from the vector int end = vec.size() - 1; auto tmp = vec[offset]; vec[offset] = vec[end]; vec.pop(); // `tmp` now contains the value removed from the std::vector
- psykotic 15y agoYeah, aside from the swap trick, there's very little to the Fisher-Yates-Knuth shuffle. It's just following the standard recursive recipe for generating permutations: to generate all permutations on n distinct elements, try every element in the first place concatenated with every permutation of the n-1 remaining elements. You can implement this directly with hash sets in O(n) time, assuming you're willing to treat hash set insertion and deletion as O(1) operations: # O(n) time def shuffle(elems): elems = set(elems) # O(n) time xs = [] while elems: x = choose(elems) # O(1) time (expected) xs.append(x) elems.remove(x) # O(1) time return xs This whole approach is obvious when you stop thinking of the problem as shuffling an array in place and start thinking of it as randomly generating a permutation of elements drawn from a set. In the final analysis, the optimized in-place implementation of the algorithm with the swap trick does provide in-place shuffling; the way the two halves of the array are used to contain respectively the partial result and an auxiliary set of remaining elements is very much like heap sort. Not coincidentally, if you interpret the algorithm as I wrote it above monadically, then it can be used to generate either a random permutation or all permutations, depending on whether choose() is interpreted in the probability monad or the list (non-determinism) monad. This shows conclusively that the shuffling algorithm is really just the standard combinatorial generation algorithm for permutations adapted to random sampling. If so, you'd also expect the swap trick to be useful for generating all permutations in place. Well, of course: void perms(int *xs, int n, int i) { if (i == n) { for (int j = 0; j < n; j++) printf("%d ", xs[j]); puts(""); return; } for (int j = i; j < n; j++) { swap(xs + i, xs + j); perms(xs, n, i + 1); swap(xs + i, xs + j); } }
- now 15y agoNice. A minor nit: it’s “ensure a fair game”, not “insure a fair game”.
- jnbiche 15y agoI love the d3.js data visualization framework, which is what Mike Bostock (the creator of d3, as it happens) used the create this page. Well done, Mike. Does anyone have suggestions for an algorithm for me to use d3.js to illustrate visually? This is such an effective learning tool that I would probably benefit from some review. I was thinking of trying a graph or tree search algorithm, maybe's Dijkstra's. Any other suggestions?
- petercooper 15y agoClustering can be visualized quite well and there are several families of algorithms that could be run over similar data, such as k-means clustering or DBSCAN.