Riffling maps in Mathematica

Question

My friend asked me this question; felt like sharing it here.

Given the deck of cards, we divided it into two groups and “alternate them”; let's call this operation "split-join". And repeat the same operation on the resulting deck.

For example, {1, 2, 3, 4} becomes {1, 2} and {3, 4} (split) and we get {1, 3, 2, 4} (join)

In addition, if we have an odd number of cards, that is {1, 2, 3} , we can split it as {1, 2} and {3} (first the big half), which leads to {1, 3, 2 } (that is, n is separated as Ceil[n/2] and n-Ceil[n/2] )

The question she asked me was:

HOW do many such split-joins take to get the original deck back?

And it became interesting to me:

If the deck has n cards, what is the number of split connections if:

• n is equal to?
• n is odd?
• n - degree "2"? [I found that then we need log (n) (base 2) the number of split-join ...]
• (Feel free to learn different scenarios like this one.)

Is there a simple template / formula / concept matching n and the number of required split connections?

I think this is a good thing to learn in Mathematica, especially since it provides the Riffle[] method.

Answer 1

an old question that I know, but it is strange that no one put the actual solution to mathematics.

  countrifflecards[deck_] := Module[{n = Length@deck , ct, rifdeck}, ct = 0; rifdeck = Riffle @@ Partition[ # , Ceiling[ n/2], Ceiling[ n/2], {1, 1}, {} ] &; NestWhile[(++ct; rifdeck[#]) &, deck, #2 != deck &,2 ]; ct] 

This handles even and odd cases:

  countrifflecards[RandomSample[ Range[#], #]] & /@ Range[2, 52, 2] 

{1, 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 28, 5, 10, 12, 36, 12, 20, 14, 12, 23, 21 , eight}

  countrifflecards[RandomSample[ Range[#], #]] & /@ Range[3, 53, 2] 

{2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 28, 5, 10, 12, 36, 12, 20, 14, 12, 23, 21, 8 , 52}

You can easily show if you added a card in an odd case, an additional card will remain at the bottom, and will not change the sequence, so the result of an odd case is only the result of n+1 .

  ListPlot[{#, countrifflecards[RandomSample[ Range[#], #]]} & /@ Range[2, 1000]] 

Answer 2

To quote MathWorld :

The amount of shuffling required to return the deck n = 2, 4, ... to the original order is 1, 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, ... (Sloane A002326), which is simply multiplicative order 2 (mod n-1). For example, a deck of 52 cards returns to its original state after eight shuffling, as 2 ** 8 = 1 (mod 51) (Golomb 1961). The smallest number of 2n cards requiring 1, 2, 3, ... shuffling to return to the initial state of the deck is 1, 2, 4, 3, 16, 5, 64, 9, 37, 6, ... (Sloane A114894).

The case when n is odd is not considered.

Note that the article also includes a Mathematica notebook with features for finding shuffle.

Answer 3

If we have an odd number of cards n==2m-1 , and if we divide the cards so that during each shuffle the first group contains cards m , the second group m-1 , and the groups are combined so that no two cards are the same group do not appear next to each other, then the number of necessary tones is equal to MultiplicativeOrder[2, n] .

To show this, we note that after one shuffle, the card that was in position k moved to position 2k for 0<=k<m and 2k-2m+1 for m<=k<2m-1 , where k is such that 0<=k<2m-1 . Written modulo n==2m-1 means that the new position is Mod[2k, n] for all 0<=k<n . Therefore, for each card to return to its original position, we need N shuffles, where N is such that Mod[2^N k, n]==Mod[k, n] for all 0<=k<n , which implies that N is any multiple of MultiplicativeOrder[2, n] .

Note that due to symmetry, the result would be exactly the same if we split the deck the other way around, that is, the first group always contains cards m-1 and the second group m . I do not know what will happen if you alternate, i.e. For strange shuffles, the first group contains m cards, and even for shuffling m-1 cards.

Answer 4

There is the old work of the magician / mathematician Percy Deaconny about restoring order with perfect shuffles. Ian Stewart wrote about this work in one of his columns, Scientific American Mathematical Resources, in 1998 - see, for example: http://www.whydomath.org/Reading_Room_Material/ian_stewart/shuffle/shuffle.html