Edit Question - KnowledgeHub

Title Body

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

Tags (comma-separated) Cancel