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