[Haskell-cafe] Re: Perfect shuffle on std. libs

[Dave Bayer]

Felipe Almeida Lessa <felipe.lessa <at> gmail.com> writes:

> I wonder why Oleg's perfect shuffle[1] isn't on any standard library?

This is incorrect terminology: A perfect shuffle is one where the cards
interleave in a 1:1:1:1:1... pattern, achieving exactly the same permutation of
the deck each time. For example, a perfect shuffle of 52 cards where the top and
bottom cards stay fixed has order 8: Do one eight times and the deck will return
to its original ordering. Most people are incapable of executing a perfect
shuffle, but various magicians have mastered this as sleight of hand. 

I am one of the authors of

  Dave Bayer, Persi Diaconis
  Trailing the dovetail shuffle to its lair
  Ann. Appl. Probab. 2 (1992), no. 2, 294-313

which found a closed form formula for the probabilities involved in riffle
shuffles, how people shuffle e.g. playing bridge. This work was summarized as
"seven shuffles suffice". I once watched my coauthor, Persi, perform a card
trick as part of a talk, where he threw in a shuffle just to amuse himself
before starting the trick. It happened to be a perfect shuffle, or the trick
would have failed. I chortled eight hours later in a solemn moment in a modern
dance concert, it took me this long to realize he had done this.

What Oleg means is that his code achieves a uniform distribution after one pass.