How many Faro shuffles for a cycle?

Question

Background

Inspired by this video by Matt Parker

A Faro shuffle is a perfect riffle shuffle where the deck is exactly interleaved with its other half. This is how to perform one:

• the deck of 52 cards is split into two piles of 26 cards each
• the two piles are interleaved. In the case of an "in" shuffle, the bottom card of the top pile ends up on the bottom, and the top card of the bottom pile ends up on the top (the outer cards move inwards). In the case of an "out" shuffle, the top card of the top pile ends up on top and vice versa (the outer cards stay on the outside).

For example, with a demonstration deck of only 6 cards, the steps are as follows:

• Start: [1, 2, 3, 4, 5, 6]
• Split: [1, 2, 3] [4, 5, 6]
• For an "in" shuffle, interleave like this: [4, 1, 5, 2, 6, 3] (zip the second half with the first half)
• For an "out" shuffle, interleave like this: [1, 4, 2, 5, 3, 6] (zip the first half with the second half)

Challenge

Given a list of values representing "in" and "out" Faro Shuffles, determine the minimum number of times that list needs to repeat such that a deck of 52 distinct cards will return to its starting arrangement. Note that this is not the same value shown in Matt's video; it is divided by the length of the input.

If the deck returns to the starting arrangement part way through the list (for example, [0, 0, 0, 0, 0, 0] (6 out shuffles) would finish after 1 full set of 6 and then 2 more shuffles), it doesn't count as having finished the cycle because it wasn't completed at the end of the list (so the output for that example would be LCM(6, 8) / 6 = 4).

Example

Input: [0, 1, 1, 0, 1, 1, 1] (using 0 for "out" shuffles and 1 for "in" shuffles, and representing the starting deck is [0, 1, 2, 3, ... 48, 49, 50, 51])

• First, we perform the shuffles as they are specified in the input: out, in, in, out, in, in, in. This gives the output:

[0, 26, 1, 27, 2, 28, 3, 29, 4, 30, 5, 31, 6, 32, 7, 33, 8, 34, 9, 35, 10, 36, 11, 37, 12, 38, 13, 39, 14, 40, 15, 41, 16, 42, 17, 43, 18, 44, 19, 45, 20, 46, 21, 47, 22, 48, 23, 49, 24, 50, 25, 51]

• Now, we check if that has caused the list to return to its exact original arrangement
• Repeat these steps, and output the number of times we've looped. In this case, it takes 1260 repetitions of [0, 1, 1, 0, 1, 1, 1], so our output is 1260

Test cases

Using 0 for "out" shuffles and 1 for "in" shuffles.

[0] 8
[1] 52
[0, 1] 252
[0, 0, 1] 20
[0, 1, 0] 20
[1, 0, 0] 20
[0, 1, 1, 0, 1, 1, 1] 1260
[0, 0, 0, 0, 0, 0, 0, 1] 2
[0, 0, 0, 0, 0, 0] 4
[0, 0, 0, 0, 0, 0, 0, 0, 0] 8
[0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1] 144
[1, 0, 1, 1, 1, 0, 1, 1, 1] 60
[0, 1, 1, 0] 44
[1, 1, 1, 1, 0, 1, 0, 1, 0] 306
[1, 1, 0, 1, 1, 0, 0, 1, 1, 0] 210
[1, 0, 0, 0, 0, 0, 0, 1] 2
[0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1] 168
[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1] 228
[1, 0, 1, 0, 1] 60
[1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1] 66
[0, 0, 0, 0, 1, 0] 252

Rules

• The values that represent "in" and "out" in the input list can be any two distinct values, within reason. For example, 0 and 1 is allowed, but code_to_do_an_in_shuffle() and code_to_do_an_out_shuffle() are not
• Standard loopholes are forbidden
• You may use any sensible I/O method
• This is code-golf, so the shortest code in bytes wins

Answer 1

Pyth, 63 53 bytes

J26AcU*J2JW=Y?@Q%ZlQ.iHG.iGH=+Z1AcYJI&qYSY!%ZlQB;/ZlQ

Try it online!

J26          # Set J to 26.
AcU*J2J      # Assign G and H to range(0, 26) and range(26, 52) respectively.
W            # While
?@Q%ZlK      # If the current element of Q (input list)
.iHG         # is 1, then interleave H and G
.iGH         # Otherwise, interleave G and H
=Y           # Assign that value to Y
=+Z1         # Increment Z by 1
AcYJ         # Now reassign G and H to the first and last 26 elements of Y respectively
I&qYSY!%ZlQB # If Y is already sorted and we are at the end of input list, then break
;/ZlQ        # Print Z divided by length of input list

Answer 2

J, ^{45 40} 36 bytes

3 :'*./#&>C.{/|.y{(,:&,&|:|.)i.2 26'

Try it online!

^{-4 thanks to xash}

Rather than use a while loop, the solution constructs the permutation, changes it to cyclic form C., and then takes the LCM *./ of the cycle lengths.

Answer 3

Python 3.8, ⁸⁸ 84 bytes

*r,=range(52)
f=lambda k,s=r:[s:=s[x::2]+s[1-x::2]for x in k[::-1]]!=s==r or-~f(k,s)

Try it online!

Uses @l4m2's neat idea (on @hyper-neutrino's answer) to reverse the shuffles instead of execute them forwards.

-4 bytes thanks to @dingledooper

Answer 4

Python 2, 100 bytes

def f(k):
 s=t=range(52);q=1
 while 1:
	for x in k[::-1]:s=s[x::2]+s[1-x::2]
	if s==t:return q
	q+=1

Try it online!

-10 bytes thanks to pxeger
-4 bytes thanks to Neil
-11 bytes thanks to l4m2
-6 bytes thanks to dingledooper

Answer 5

Charcoal, 47 35 bytes

Ｗ¬⁼ω⁺αβ«⊞υωＦ⮌θ≔⭆²Φ∨ω⁺αβ﹪⁺κ⁺λξ²ω»ＩＬυ

Try it online! Link is to verbose version of code. Edit: Saved 12 bytes thanks to @l4m2 by performing in-sorts and out-sorts instead, but the input values are now 0 for an in-shuffle and 1 for an out-shuffle. Explanation:

Ｗ¬⁼ω⁺αβ«

Repeat until the shuffle reaches the initial pack, represented here by the concatenation of the upper and lower case letters.

⊞υω

Keep track of the number of cycles.

Ｆ⮌θ

Loop over each type of shuffle in reverse, since we're performing inverse shuffles.

≔⭆²Φ∨ω⁺αβ﹪⁺κ⁺λξ²ω

Take alternating cards from the pack (initialising it on the first pass). Whether odd or even cards are taken first depends on the type of shuffle. The remaining cards are then concatenated, completing the in-sort or out-sort.

»ＩＬυ

Output the number of shuffles needed.

Answer 6

Ruby, 86 80 77 bytes

->s{r=k=[*0..51];1.step.find{s.map{|c|r=k.map{|v|r[(v/2+26*v+=c)%52]}};r==k}}

Try it online!

Answer 7

Husk, 13 bytes

Γ€GFöΣT*½ḣ52∞

Try it online! or Verify all tests

15 bytes, 16 bytes, 16 bytes

input taken as 1 instead of 0 and -1 instead of 1.

-2 bytes from Leo.

This could be another 15 bytes, but times out.

Explanation

Γ€GFöΣT*½ḣ52∞
            ∞ infinite list of repetitions of the input
  G           scan from left with:
         ḣ52  1..52 as the start value
   Fö          fold the repeated list with
               the current value as start
               and do the following:
        ½       split in two halves
       *        multiply by the list number
      T         transpose
     Σ          flatten
Γ              take first element and:
 €             find its index in the remaining list

Answer 8

JavaScript (Node.js), 102 99 98 95 bytes

f=s=>s.map(v=>L=L.map((_,i)=>L[i+52*(i%2^v)>>1]))|L+[]==G||1+f(s);L=G=[...Array(52)].map(Array)

Try it online!

Answer 9

Wolfram Language, 97 bytes

s|->Length@NestWhileList[Fold[Riffle@@#~TakeDrop~26~RotateLeft~#2&,#,s]&,Range[52],UnsameQ,All]-1

Try it online! (uses \[Function] rather than |->, as TIO doesn't have the most recent version of the language)

Answer 10

Jelly, 15 bytes

ØẠŒHṚ⁹¡ż/Fʋƒ@ƬL

A monadic Link accepting a list of 1s (in) and 0s (outs) which yields a positive integer (number of repetitions of the described procedure required to reset the deck of 52 cards).

Try it online!

How?

Just repeatedly executes the instructions list until reset has occured...

ØẠŒHṚ⁹¡ż/Fʋƒ@ƬL - Link: list, shuffles
ØẠ              - "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" ...26*2=52 :)
             Ƭ  - collect up starting with that "deck" until a repetition occurs using:
            @   -   with reversed arguments - f(shuffles,deck)
           ƒ    -     reduce using (X) as the initial value with:
          ʋ     -       last four links as a dyad - f(current_deck, current_shuffle):
  ŒH            -         split (current_deck) into two halves
      ¡         -         repeat...
     ⁹          -           ...number of times: right argument = current_shuffle
    Ṛ           -           ...action: reverse
        /       -         reduce using:
       ż        -           zip together
         F      -         flatten
              L - length

Answer 11

R, 80 bytes

o=scan();e=d=0:51;while({for(s in o)d=t(matrix(d,26,3)[,1:2+s]);sd(d-e)})T=T+1;T

Try it online!

Implements riffle shuffle by re-arranging the deck into a matrix with 26 rows, and transposing.
An 'in' shuffle first reverses the columns, which is achieved in R by making a 3-column matrix (which gets filled by recycling elements), and then selecting columns 2,3.

e=d=0:51                # set e,d to the initial order of the deck
while({                 # while loop: 
  for(s in o)           #  first cycle through the shuffle-types in o
    d=                  #  reordering d each time
      t(                #  as the transpose of
        matrix(d,26,    #  a matrix with 26 rows
        3)              #  and 3 columns (so the third column is the first one again)
          [,1:2+s])     #  selecting columns 1:2 if o==0, 
                        #  or columns 2:3 (same as 2:1) if o==1;
  sd(d-e)}              #  then repeat until standard deviation of d-e is non-zero
                        #  (d & e are both permutations of the deck,
                        #  so sum(d-e) must be zero, and sd(d-e) can only
  )                     #  be zero if d==e)
  T=T+1                 # increment T (from initial value of 1) each loop
T                       # and finally output the value of T

Answer 12

PowerShell 7, 87 84 bytes

for(;"$c"-ne0..51;$x++){$args|%{$s=$_
$c=$c ??0..51|%{(2*$_+($s,!$s)[$_/51])%52}}}$x

Try it online! (Link is to a TIO-compatible version with 4 additional bytes; PowerShell 6 and below do not support the null-coalescing operator ??)

Answer 13

Python 3, 136 bytes

-5 thanks to OP

Can definitely be golfed more, but I'm too tired.

def f(s):
 o=l=[*range(52)];c=0
 while 1:
  for i in s:l=[(l[:26],l[26:])[j%2-i][j//2]for j in range(52)]
  c+=1
  if l==o:return c

Try it online!

Answer 14

Haskell, 91 bytes

f l=[r|r<-[1..],and[foldl(\x i->mod(2*x+mod(div x 26+i)2)52)y([1..r]>>l)==y|y<-[0..51]]]!!0

Try it online!

f takes l as a list of 0s and 1s, with the format described in the statement.

Answer 15

C (gcc), ^{194 \$\cdots\$ 180} 174 bytes

Saved 6 bytes thanks to ceilingcat!!!

w=52;n;c;i;j;a[156];f(s,l)int*s;{for(c=i=0;i<w*3;)a[n=i++]=i%w;for(;n;++c)for(j=0;j<l;++j)for(i=!wmemcpy(a+w,a,w);i<w;n=wmemcmp(a,a+2*w,w))a[i++]=a[w+(s[j]+i&1)*26+i/2];n=c;}

Try it online!

Inputs a pointer to the shuffle array and its length (since pointers in C carry no length info).

Explanation (before some golfs)

w=52;n;c;i;j;                              // declare needed vars   
f(s,l)int*s;{                              // main function
    char a[w],b[w],e[w];                   // declare arrays for shuffling  
    for(c=i=0;i<w;)a[i++]=e[i]=i;          // init a and e to 0..51
    for(n=1;n;++c)                         // loop until array a is back 
                                           // to its original order (n == 0)
                                           // c counts iterations
        for(j=0;j<l;++j)                   // loop over shuffle array  
            for(i=!memcpy(b,a,w);          // copy a over to b (returns !0)  
                                 i<w;      // loop over a and b   
                          n=memcmp(a,e,w)) // here's a good place to calc n 
              a[i++]=                      // set each element in a to
                     b[                   ]// an element in b depending on
                       ((s[j]+i)%2)*26+i/2 // our current shuffle and i   
    n=c;                                   // return count  
}