Card Shuffling Visualizations

Year: 2018 Authors: Roger Antonsen

Core claim

Carefully designed permutation visualizations can make card-shuffle properties and symmetry patterns visible that are otherwise hard to see.

Topics

card shuffles, permutation diagrams, shuffle order, central symmetry, visual mathematics

Domains

permutations, modular arithmetic, group composition, number theory, data visualization, computer-generated art, information design, algorithmic graphics

Methods

stacked diagrams, colored curves, repeated shuffle visualization, Processing sketches

Media

playing cards, digital diagrams, Processing

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2018 Conference Proceedings

Card Shuffling Visualizations

Roger Antonsen

University of Oslo, Norway; rantonse@ifi.uio.no

Abstract

This paper discusses a few natural ways to visualize card shuffles, like the perfect in- and out-shuffle and the milk shuffle. These visualizations are designed to highlight interesting properties of the shuffles, like the order of the shuffles and the stay-stack principle. Such properties have attracted magicians and mathematicians alike, and visualizations like these make it possible to see properties that would have been hard to see otherwise.

Four Ways to Shuffle a Deck of Cards

Imagine that you have a deck of cards, say eight cards numbered from 0 to 7: [0, 1, 2, 3, 4, 5, 6, 7]. Split the deck precisely into two halves, [0, 1, 2, 3] and [4, 5, 6, 7], and then interleave the cards evenly such that the top card remains at the top and the bottom card remains at the bottom. The result is [0, 4, 1, 5, 2, 6, 3, 7]. This is called a perfect out-shuffle. The corresponding perfect in-shuffle is the interleaving of the two halves such that the top card becomes the second card from the top: [4, 0, 5, 1, 6, 2, 7, 3]. (Perfect shuffles are also referred to as faro shuffles.) Another way to shuffle a deck is to give it a cut. This is where the top part of the deck, say [0, 1], is placed at the bottom, giving us [2, 3, 4, 5, 6, 7, 0, 1]. Finally, we have the milk shuffle. This is where we repeatedly pinch the deck and pull off the top and the bottom card into a separate pile. This move, often referred to as milking the deck, is repeated until all the cards have been pulled off. In this case, the first pair of cards to be pulled off is [0, 7]. Then, [1, 6], [2, 5], and finally [3, 4], which becomes the two top cards: [3, 4, 2, 5, 1, 6, 0, 7]. A nice and clean way to visualize these shuffles is with the following type of diagrams:

perfect out-shuffle

perfect in-shuffle

two-card cut

milk shuffle

The top rows represent the cards in a deck before each shuffle, and the bottom rows represent the order after each shuffle. Observe for example that in a perfect out-shuffle, the top card remains on the top, while in a perfect in-shuffle, the top card becomes the second card. The diagrams may also be read from below, or - equivalently - turned upside-down, in which case the shuffles are called the respective reverse shuffles. A reverse perfect shuffle occurs naturally when cards are being dealt or separated into distinct piles.

Permutations and the Order of Card Shuffles

From a mathematical point of view each shuffle is a permutation of the cards, and repeated shuffling can be viewed as the composition of permutations. Visually, this corresponds to stacking diagrams like this on top of each other. In more mathematical terms, the perfect out-shuffle on a deck of $N$ cards, where $N$ is even, moves the card in position $p$ to the position $\mathbf{O}(p)\equiv 2p(\mathrm{mod}N-1)$ for all $p$ less than $N-1$ and to $\mathbf{O}(N-1)=N-1$ when $p$ is $N-1$ . In a similar way, the perfect in-shuffle moves the card in position $p$ to $\mathbf{I}(p)\equiv 2p+1(\mathrm{mod}N+1)$ . A cut of $c$ cards simply moves the card in position $p$ to $\mathbf{C}(p)\equiv p-c(\mathrm{mod}N)$ .

Antonsen

We will now consider what happens as we repeat the various shuffles. After a certain number of repetitions, called the order of each shuffle, the deck will return to its original order. The order of a particular shuffle depends on the number of cards: For eight cards, this happens after three times for the out-shuffle, six times for the in-shuffle, four times for the two-card cut, and four times for the milk shuffle:

3 out-shuffles with 8 cards

6 in-shuffles with 8 cards

4 two-card cuts with 8 cards

4 milk shuffles with 8 cards

Choices for Visualizations

While pleasing to look at in their own right, we can do much more in terms of visualizing the underlying structures of each shuffle. Two obvious things we can do is to color the dots and the curves in various ways. There are numerous possibilities for the size, shape, and color of the dots and curves, and these are just a few:

(a) 8 out-shuffles with 52 cards dots: black curves: black

(b) 8 out-shuffles with 52 cards dots: light-to-dark curves: faded

(c) 8 out-shuffles with 52 cards dots: light-dark-light curves: light-dark

(d) 8 milk shuffles with 43 cards dots: light-dark curves: light-dark

In all of these examples, the original order of the cards is restored after eight shuffles. In (a), (b) and (c), the shuffles are all perfect out-shuffles with 52 cards. For comparison, the shuffle in (d) is a milk shuffle with 43 cards. In (a), there is no particular coloring; consequently, all we see is an identical permutation being repeated eight times. In (b), the dots are colored from light to dark, while the lines are faded to give emphasis to the dots. The coloring of the dots makes it easier to see what the perfect out-shuffle actually does to the cards. For example, we can easily see the intermediate orderings and that the original ordering has been restored after eight times. In (c) the dots are colored from light to dark and back again, which is motivated in the next section, while the curves are colored from light to dark. In this way, it becomes apparent that the cards are being weaved together. In (d), both the dots and the curves are colored from light to dark.

Card Shuffling Visualizations

Visualizing the Stay-Stack Principle

There are many interesting mathematical facts about card shuffling. One is the so-called stay-stack principle: If a deck of cards is arranged such that each card $n$ from the top is matching the corresponding card $n$ from the bottom, then the deck is said to have central symmetry. The stay-stack principle is that any number of perfect in- or out-shuffles preserves this central symmetry. The following three diagrams illustrate repeated perfect out-shuffles until the original order of the deck is restored. The dots are colored from light to dark and back again. Each curve is colored as the opposite of its starting point. Observe that all the diagrams have a left-right symmetry due to the initial coloring and the stay-stack principle.

5 out-shuffles with 32 cards

6 out-shuffles with 64 cards

7 out-shuffles with 128 cards

8 out-shuffles with 256 cards

Forcing a Card to the Top

It is now a well-established fact (see [3] for details) that any card in any deck can be forced to the top by an appropriate combination of perfect in- and out-shuffles. The history of this problem goes back to the magician and computer programmer, Alex Elmsley, who in 1957 published a method for forcing the top card to any position in a deck. See [1] for a fun typographical application of this principle.

Let us here illustrate a related property of perfect shuffles, which has a similar feel to it: In a deck of $N$ cards, where $N$ is odd, if $2^k\equiv 1(\mathrm{mod}N)$ , then any sequence of $k$ perfect in- and out-shuffles corresponds to cutting the deck somewhere. (For details, see [4].)

For example, in a deck of 51 cards, any combination of eight perfect in- and out-shuffles corresponds to a cut. The calculation checks out: $2^8=256\equiv 1(\mathrm{mod}51)$ . In the illustration to the right, the sequence out-out-out-in-out-out-out-in of perfect shuffles leads to a cut of 17 cards from the bottom of the deck. It is no coincidence that $17_{10}=00010001_2$ . A different combination of in- and outshuffles will lead to a different cut. In this example, the result is that card 35 ends up at the top of the deck.

8 perfect out-and in-shuffles forcing card 35 to the top

Antonsen

Generalizations

Perfect in- and out-shuffles, as well as several other shuffles, may be generalized to any number of cards and any number of piles. Here are two examples that I like, with 10 and 5 piles, respectively:

4 in-shuffles with 100 cards and 10 piles

6 in-shuffles with 125 cards and 5 piles

Conclusions and Acknowledgments

The inspiration for this work came from attending a talk by Perci Diaconis [2] last year. I wanted to know if I could understand the mathematics of card shuffling better through appropriate visualizations, so I programmed a sketch in Processing [5]. My motivation was to see some of the underlying structure that would be hard to see otherwise, much like with fractals and other computer-generated art. I find the process of visualizing and experimenting with mathematical structures through computer code, rewarding and exciting. These permutation diagrams are nice examples of how code can be utilized in order to visualize, and make tangible, mathematical structures, and also uncover some of that underlying beauty and complexity that often follow from very simple assumptions, in this case specific permutations corresponding to card shuffles.

References

[1] E. D. Demaine and M. L. Demaine. “Juggling and Card Shuffling Meet Mathematical Fonts.” in Connections in Discrete Mathematics: In Honor of Ron Graham’s 80th Birthday. Cambridge University Press, to appear. [2] P. Diaconis. “The Magic of Charles S. Peirce.” Mathematical Sciences Research Institute. April 2017. [3] P. Diaconis and R. Graham. “The Solutions to Elmsley’s Problem.” Math Horizons, vol. 14, no. 3, 2007, pp. 22-27. [4] S. Morris. Magic Tricks, Card Shuffling and Dynamic Computer Memories. ser. MAA Spectrum. Mathematical Association of America, 1998. [5] Processing. https://processing.org/.