Just as background, I'm aware of the Fisher-Yates perfect shuffle. It is a great shuffle with its O(n) complexity and its guaranteed uniformity and I'd be a fool not to use it ... in an environment that permits in-place updates of arrays (so in most, if not all, imperative programming environments).

Sadly the functional programming world doesn't give you access to mutable state.

Because of Fisher-Yates, however, there's not a lot of literature I can find on how to design a shuffling algorithm. The few places that address it at all do so briefly before saying, in effect, "so here's Fisher-Yates which is all the shuffling you need to know". I had to, in the end, come up with my own solution.

The solution I came up with works like this to shuffle any list of data:

  • If the list is empty, return the empty set.
  • If the list has a single item, return that single item.
  • If the list is non-empty, partition the list with a random number generator and apply the algorithm recursively to each partition, assembling the results.

In Erlang code it looks something like this:

shuffle([])  -> [];
shuffle([L]) -> [L];
shuffle(L)   ->
  {Left, Right} = lists:partition(fun(_) -> 
                                    random:uniform() < 0.5 
                                  end, L),
  shuffle(Left) ++ shuffle(Right).

(If this looks like a deranged quick sort to you, well, that's what it is, basically.)

So here's my problem: the same situation that makes finding shuffling algorithms that aren't Fisher-Yates difficult makes finding tools to analyse a shuffling algorithm equally difficult. There's lots of literature I can find on analysing PRNGs for uniformity, periodicity, etc. but not a lot of information out there on h

algorithm functional-programming shuffle
Edit
Report