## Perfect Shuffle

### March 13, 2020

This is easy if we use our Standard Prelude:

(define (faro xs) (let-values (((f r) (split (/ (length xs) 2) xs))) (flatten (zip f r))))

(define (perf n) (let ((ds (range n))) (do ((xs (faro ds) (faro xs)) (k 1 (+ k 1))) ((equal? xs ds) k))))

> (faro (range 1 8)) (1 5 2 6 3 7 4 8) > (faro (faro (faro (range 1 8)))) (1 2 3 4 5 6 7 8) > (perf 8) 3 > (perf 52) 8

If you don’t use the Standard Prelude, and limit yourself to the functions of R4RS Scheme, it takes a little bit more work:

(define (deck n) (let loop ((n n) (ds (list))) (if (zero? n) ds (loop (- n 1) (cons n ds)))))

(define (faro xs) (let loop1 ((ts xs) (hs xs) (ys (list))) (if (and (pair? hs) (pair? (cdr hs))) (loop1 (cdr ts) (cddr hs) (cons (car ts) ys)) (let loop2 ((xs (reverse ts)) (ys ys) (zs (list))) (if (null? xs) zs (loop2 ys (cdr xs) (cons (car xs) zs)))))))

(define (perf n) (let ((ds (deck n))) (do ((xs (faro ds) (faro xs)) (k 1 (+ k 1))) ((equal? xs ds) k))))

> (perf 52) 8

You can run the program at https://ideone.com/8C1PJb.

Cool drill. Here is my take on it using Julia: https://pastebin.com/ppSpZ5BH

For a 52 card deck, it takes just n = 8 perfect shuffles, while for a 54 card one (one which includes 2 jokers) it takes many more.

Have a nice weekend and stay healthy!

In Python.

Here is a simple solution in R7RS Scheme and a few popular helpers.

It includes a formulaic method for computing the cycle-length in

addition to the explicit one.

Output:

Looking at the pattern of numbers, it seems it is sometimes possible to calculate the number of perfect shuffles with an equation instead of actually doing the perfect shuffles.

For an even number N and N-1, they will both have the same answer.

E.g. 52 and 51 both take 8 perfect shuffles

I’ve also noticed for any number that is 2^n, the number of perfect shuffles is n.

E.g. 8 = 2^3, n=3, so the number of perfect shuffles is 3.

For any number that is (2^n) + 2 or 2^n + 1, the answer is 2n.

E.g. 10 = (2^3)+2, n = 3. The answer is 2n = 6.

Also: 9 = (2^3)+1, n = 3. The answer is 2n = 6.

Unfortunately, I can’t figure out the pattern beyond that, but in these special cases, the number of perfect shuffles can be found in O(1) time.

If there is an equation to describe the entire pattern, perhaps all cases could be solved in O(1) time.

Code:

import numpy as np

import math

#In some cases, we do not need to actually perform the perfect shuffle: we can determine the answer with simple math

def checkSpecialCases(arr):

#An even number N will have the same solution as N-1

#Add 1 to odd numbers to make checks easier

N = len(arr) + len(arr)%2

def perfectShuffle(arr):

orig = np.copy(arr)

if

name== ‘main‘:for i in range(2,9):

arr = np.arange(1,i+1)

print(str(i) + ‘ : ‘ + str(checkSpecialCases(arr)))

Output:

2 : 1

3 : 2

4 : 2

5 : 4

6 : 4

7 : 3

8 : 3

Quoting Programming Praxis :

Further;If the aim of shuffling is to make the card order unpredicatable or at least difficuld to predict; how many “faro-shuffles” of a 52-card stack is ideal ?

> programmingpraxis posted: “A perfect shuffle, also known as a faro > shuffle, splits a deck of cards into equal halves (there must be an > even number of cards), then perfectly interleaves them. Eventually a > series of perfect shuffles returns a deck to its original order. For > instance,” > > > T

Here’s a solution in C.

Example:

As indicated on Wikipedia, this matches sequence A002326 on OEIS.

Here’s a Haskell version. Instead of shuffling an actual list I use the formulas from the “Faro shuffle” Wikipedia page.

I had fun with this one:

Klong version

Klong version

Sorry for lack of formatting, new to the site. This is a vanilla Python solution; I was stumped for a bit but figured it out pretty quickly after drawing out a couple of cards and seeing how they moved.

Number of shuffles for 52 cards: 8

for i in range(2, 14, 2):

# Initialize deck size

deck_size = i

if deck_size % 2 != 0:

msg = “Deck size must be even”

raise ValueError(msg)

=====================================

OUTPUT

For a deck of 2 cards, it takes 1 perfect shuffles to return to its original permutation.

For a deck of 4 cards, it takes 2 perfect shuffles to return to its original permutation.

For a deck of 6 cards, it takes 4 perfect shuffles to return to its original permutation.

For a deck of 8 cards, it takes 3 perfect shuffles to return to its original permutation.

For a deck of 10 cards, it takes 6 perfect shuffles to return to its original permutation.

For a deck of 12 cards, it takes 10 perfect shuffles to return to its original permutation.

@Sam – to format code, put ‘[code lang=”python”]’ on a line at the start of the block of code, and ‘[/code]’ on a line at the end.

Just to be clear – don’t include the single quotes there, just the square brackets and the stuff inside:

Racket: https://github.com/xojoc/programming-challenges/blob/master/programming-praxis/2020_03_13.rkt