# How many Faro shuffles for a cycle?

## 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 , so the shortest code in bytes wins
• Commented May 3, 2021 at 13:21
• What is the expected answer for [0, 0, 0, ... 9 times]? 0 or 8? Note that it returns to the starting arrangement before the first cycle finishes. Commented May 3, 2021 at 13:50
• @ManishKundu The way I interpret it is that it needs to complete the list. Commented May 3, 2021 at 13:51
• @Jonah I'm going to say no, since it kind of defeats the background of the challenge, which is to simulate weird shuffling in card games Commented May 3, 2021 at 16:13
• Random side note: the largest possible output is 180,180 (the largest order of a permutation of 52 objects) ... I wonder if there is an input that yields that. Commented May 4, 2021 at 1:21

# 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


# 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.

• (,:&,&|:|.)i.2 26 to save 4
– xash
Commented May 3, 2021 at 15:17

# Python 3.8, 88 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

• You can use *r,=range(52)instead to save 4 bytes. Commented May 3, 2021 at 17:56

# 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

• This can be shorter by copying the initial range and comparing against that instead of sorting it: Try it online! Commented May 3, 2021 at 14:09
• @pxeger Oh, good idea, thanks. (Got it to 123 bytes in py 2 using the same idea) Commented May 3, 2021 at 14:10
• You can use range(52) instead of range(1,53): Try it online! Commented May 3, 2021 at 14:12
• @pxeger oh oops, that was for testing lol. thanks Commented May 3, 2021 at 14:12
• Reversed moves
– l4m2
Commented May 3, 2021 at 15:59

# 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.

# 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!

• 83 bytes by copying the initial range and comparing against that instead of the sorted array Commented May 3, 2021 at 13:59
• You need to include the assignment f= as part of the code because you recurse using it, by the way Commented May 3, 2021 at 14:01

# Husk, 13 bytes

Γ€GFöΣT*½ḣ52∞


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


# JavaScript (Node.js), 1029998 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!

# 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)

# 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


# 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


# 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 ??)

# 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!

• The list comprehension part instead of zip is really smart! You don't need o=l[:] since you never mutate l (only reassign) - it can just be o=l=[*range(52)]. This allows you to replace the second range(52) with just o Also, in Python 2 you could drop the [*] because range returns a list already, change // to /, and save some with tab indentation: Try it online! Commented May 3, 2021 at 14:18
• Ohh, I was thinking about the horrors of how pointers to the same object cause headaches so I think I did that by habit. I'll fix it. Commented May 3, 2021 at 14:24
• There's no room for best practices in code golf! :-) Commented May 3, 2021 at 14:26
• I remember the days of onelinerizer.com before I discovered code golf Commented May 3, 2021 at 14:28
• There are still a few low-hanging fruit here; not sure if you missed them in my previous comment Commented May 3, 2021 at 14:30

# 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.

# 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
}

• Suggest bcmp(x,y,z*4) instead of wmemcmp(x,y,z) Commented Oct 25, 2022 at 18:31