[Haskell-cafe] Re: Perfect shuffle on std. libs
bayer at math.columbia.edu
Sat Jul 14 23:46:12 EDT 2007
Felipe Almeida Lessa <felipe.lessa <at> gmail.com> writes:
> I wonder why Oleg's perfect shuffle 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.
More information about the Haskell-Cafe