Show HN: A visual explanation of Fisher–Yates shuffle

I 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.

Most 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.

Point taken; I'll keep this in mind in future examples. I find it extremely tempting to write JavaScript as compact as possible, sometimes at the expense of readability. Writing pedagogical code requires a slightly different mindset.

It doesn't bother me to read other people's code that does this, but I never decrement or increment within an assignment statement. I've just made too many off by one, index out of bounds errors over the years.

I generally don't use it too much myself because I agree it tends to add a bit of confusion. A tiny bit but still.

I think that in that particular case the fact the array[m] is used in the next line makes things not as obvious as they could be visually. I feel that the following requires less reading:

  m -=1;
  t = array[m];
  array[m] = array[i];
  array[i] = t;

To me, it's faster to parse.

And 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.

Attaching 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.

To 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.

Yeah, 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);
        }
    }

Clustering 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.

The 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.

Repeatedly sampling from a uniform distribution gives a uniform distribution - uniform means the probability is the same for all cards.

That's not how central tendency works. The average position converges to a normal.

It uses d3.js, which pretty much requires a modern browser with SVG. I suspect you will find it doesn't work on IE8.

Nevermind. 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.

The 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.