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

I find it a bit hard to see how to reinterpret your Python code in the list monad. Can you post a Haskell version of this function?

Hey, sorry for the late reply.

It seems pretty obvious to me, so I'm not sure what is confusing you.

    class Monad m => ChoiceMonad m where
        choice :: [a] -> m a

For the list monad, choice is just the identity function. For the probability monad, choice picks a random element from the list. (Ideally choice would take a random access structure like a set as its argument, but I'm doing it the simplest way here.)

To implement shuffle, you more or less just transliterate the Python code as you'd expect.

Before you tackle this, make you sure completely understand how the same situation plays out for the simpler case of subsets:

    subset        :: ChoiceMonad m => [a] -> m [a]
    subset []     = return []
    subset (x:xs) = do b <- choice [True, False]
                       xs' <- subset xs
                       return (if b then x:xs' else xs')

Over the list monad, this generates a list of all subsets. Over the probability monad, it generates a random subset.

Thank you, now I see. Here's my version:

    shuffle :: (ChoiceMonad m, Eq a) => [a] -> m [a]
    shuffle [] = return []
    shuffle elems = do 
      x <- choice elems
      xs <- shuffle (x `delete` elems)
      return (x:xs)