In-shuffles and out-shuffles

The previous post talked about doing perfect shuffles: divide a deck in half, and alternately let one card from each half fall.

It matters which half lets a card fall first. If the top half's bottom card falls first, this is called an in-shuffle. If the bottom half's bottom card falls first, it's called an out-shuffle.

With an out-shuffle, the top and bottom cards don't move. Presumably it's called an out-shuffle because the outside cards remain in place.

An out-shuffle amounts to an in-shuffle of the inner cards, i.e. the rest of the deck not including the top and bottom card.

The previous post had a Python function for doing an in-shuffle. Here we generalize the function to do either an in-shuffle or an out-shuffle. We also get rid of the list comprehension, making the code longer but easier to understand.

def shuffle2(deck, inside = True): n = len(deck) top = deck[: n//2] bottom = deck[n//2 :] if inside: first, second = bottom, top else: first, second = top, bottom newdeck = [] for p in zip(first, second): newdeck.extend(p) return newdeck

Let's use this code to demonstrate that an out-shuffle amounts to an in-shuffle of the inner cards.

deck = list(range(10))d1 = shuffle2(deck, False) d2 = [deck[0]] + shuffle2(deck[1:9], True) + [deck[9]]print(d1)print(d2)

Both print statements produce [0, 5, 1, 6, 2, 7, 3, 8, 4, 9].

I said in the previous post that k perfect in-shuffles will restore the order of a deck of n cards if

2^k= 1 (modn+ 1).

It follows that k perfect out-shuffles will restore the order of a deck of ncards if

2^k= 1 (modn - 1)

since an out-shuffle ofn cards is essentially an in-shuffle of the n - 2 cards in the middle.

So, for example, it only takes 8 out-shuffles to return a deck of 52 cards to its original order. In the previous post we said it takes 52 in-shuffles, so it takes a lot fewer out-shuffles than in-shuffles.

It's plausible to conjecture that it takes fewer out-shuffles than in-shuffles to return a deck to its initial order, since the former leaves the two outside cards in place. But that's not always true. It's true for a deck of 52 cards, but not for a deck of 14, for example. For a deck of 14 cards, it takes 4 in-shuffles or 12 out-shuffles to restore the deck.

The post In-shuffles and out-shuffles first appeared on John D. Cook.