Perfect shuffle

Perfect shuffle is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

A deck can be divided in two halves:

   a b c d e f -> a b c | d e f

Perfect shuffling means taking one card from the first half, one card for the second half, and so on:

   a d b e c f

Perfect shuffling can be done only with an even number of cards.

A remarkable feature of perfect shuffling is that the deck goes back to the start after a number that is fixed for every n (where n is the number of cards)

• Implement a magic shuffle function
• Print the number of perfect shuffles needed to go back to start for decks from 2 to 10,000 cards (by steps of 2), determined by using the magic shuffle function

PARI/GP

<lang parigp>magic(v)=vector(#v,i,v[if(i%2,1,#v/2)+i\2]); shuffles_slow(n)=my(v=[1..n],o=v,s=1);while((v=magic(v))!=o,s++);s; shuffles(n)=znorder(Mod(2,n-1)); vector(5000,n,shuffles_slow(2*n))</lang>

Output:

%1 = [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, 8, 52, 20, 18, 58, 60, 6, 12, 66, 22, 35, 9, 20, 30, 39, 54
, 82, 8, 28, 11, 12, 10, 36, 48, 30, 100, 51, 12, 106, 36, 36, 28, 44, 12, 24, 1
10, 20, 100, 7, 14, 130, 18, 36, 68, 138, 46, 60, 28, 42, 148, 15, 24, 20, 52, 5
2, 33, 162, 20, 83, 156, 18, 172, 60, 58, 178, 180, 60, 36, 40, 18, 95, 96, 12,
196, 99, 66, 84, 20, 66, 90, 210, 70, 28, 15, 18, 24, 37, 60, 226, 76, 30, 29, 9
2, 78, 119, 24, 162, 84, 36, 82, 50, 110, 8, 16, 36, 84, 131, 52, 22, 268, 135,
12, 20, 92, 30, 70, 94, 36, 60, 136, 48, 292, 116, 90, 132, 42, 100, 60, 102, 10
2, 155, 156, 12, 316, 140, 106, 72, 60, 36, 69, 30, 36, 132, 21, 28, 10, 147, 44
, 346, 348, 36, 88, 140, 24, 179, 342, 110, 36, 183, 60, 156, 372, 100, 84, 378,
 14, 191, 60, 42, 388, 88, 130, 156, 44, 18, 200, 60, 108, 180, 204, 68, 174, 16
4, 138, 418, 420, 138, 40, 60, 60, 43, 72, 28, 198, 73, 42, 442, 44, 148, 224, 2
0, 30, 12, 76, 72, 460, 231, 20, 466, 66, 52, 70, 180, 156, 239, 36, 66, 48, 243
, 162, 490, 56, 60, 105, 166, 166, 251, 100, 156, 508, 9, 18, 204, 230, 172, 260
, 522, 60, 40, 253, 174, 60, 212, 178, 210, 540, 180, 36, 546, 60, 252, 39, 36,
556, 84, 40, 562, 28, 54, 284, 114, 190, 220, 144, 96, 246, 260, 12, 586, 90, 19
6, 148, 24, 198, 299, 25, 66, 220, 303, 84, 276, 612, 20, 154, 618, 198, 33, 500
, 90, 72, 45, 210, 28, 84, 210, 64, 214, 28, 323, 290, 30, 652, 260, 18, 658, 66
0, 24, 36, 308, 74, 60, 48, 180, 676, 48, 226, 22, 68, 76, 156, 230, 30, 276, 40
, 58, 700, 36, 92, 300, 708, 78, 55, 60, 238, 359, 51, 24, 140, 121, 486, 56, 24
4, 84, 330, 246, 36, 371, 148, 246, 318, 375, 50, 60, 756, 110, 380, 36, 24, 348
, 384, 16, 772, 20, 36, 180, 70, 252, 52, 786, 262, 84, 60, 52, 796, 184, 66, 90
, 132, 268, 404, 270, 270, 324, 126, 12, 820, 411, 20, 826, 828, 92, 168, 332, 9
0, 419, 812, 70, 156, 330, 94, 396, 852, 36, 428, 858, 60, 431, 172, 136, 390, 1
32, 48, 300, 876, 292, 55, 882, 116, 443, 21, 270, 414, 356, 132, 140, 104,[+++]

(By default gp won't show more than 25 lines of output, though an arbitrary amount can be printed or written to a file; use print, write, or default(lines, 100) to show more.)

Python

<lang python> import doctest import random

def flatten(lst):

   """
   >>> flatten([[3,2],[1,2]])
   [3, 2, 1, 2]
   """
   return [i for sublst in lst for i in sublst]

def magic_shuffle(deck):

   """
   >>> magic_shuffle([1,2,3,4])
   [1, 3, 2, 4]
   """
   half = len(deck) // 2 
   return flatten(zip(deck[:half], deck[half:]))

def after_how_many_is_equal(shuffle_type,start,end):

   """
   >>> after_how_many_is_equal(magic_shuffle,[1,2,3,4],[1,2,3,4])
   2
   """

   start = shuffle_type(start)
   counter = 1
   while start != end:
       start = shuffle_type(start)
       counter += 1
   return counter

def main():

   doctest.testmod()

   print("Length of the deck of cards | Perfect shuffles needed to obtain the same deck back")
   for length in range(2,10**4,2):
       deck = list(range(length))
       shuffles_needed = after_how_many_is_equal(magic_shuffle,deck,deck)
       print("{} | {}".format(length,shuffles_needed))

if __name__ == "__main__":

   main()

</lang> Reversed shuffle or just calculate how many shuffles are needed: <lang python>def mul_ord2(n): # directly calculate how many shuffles are needed to restore # initial order: 2^o mod(n-1) == 1 if n == 2: return 1

n,t,o = n-1,2,1 while t != 1: t,o = (t*2)%n,o+1 return o

def shuffles(n): a,c = list(range(n)), 0 b = a

while True: # Reverse shuffle; a[i] can be taken as the current # position of the card with value i. This is faster. a = a[0:n:2] + a[1:n:2] c += 1 if b == a: break return c

for n in range(2, 10000, 2): #print(n, mul_ord2(n)) print(n, shuffles(n))</lang>

Racket

With an overwhelming urge to say that math/number-theory rocks! <lang racket>#lang racket (require math/number-theory)

COMMENTS

Number of riffle shuffles of 2n+2 cards required to return a deck to initial state.

(define (A002326 2n+2)

 (unit-group-order 2 (- 2n+2 1)))

(define (perfect-shuffle l)

 (define-values (as bs) (split-at l (/ (length l) 2)))
 (foldr (λ (a b d) (list* a b d)) null as bs))

(define (magic-shuffle n)

 (for/fold ((d (range n))) ((s (A002326 n)))
   (printf "shuffle#~a:\tdeck: ~a~%" s d)
   (perfect-shuffle d)))

(magic-shuffle 10) (magic-shuffle 14)

(define magic-numbers (for/list ((n (in-range 2 10001 2))) (A002326 n)))

(append (take magic-numbers 50) (list '...) (take-right magic-numbers 50))

(module+ test

 (require tests/eli-tester)
 (test
  (for/list ((i (in-range 2 16 2))) (A002326 i)) => '(1 2 4 3 6 10 12)
  (perfect-shuffle '(1 2 3 4)) => '(1 3 2 4)))</lang>

Output:

shuffle#0:	deck: (0 1 2 3 4 5 6 7 8 9)
shuffle#1:	deck: (0 5 1 6 2 7 3 8 4 9)
shuffle#2:	deck: (0 7 5 3 1 8 6 4 2 9)
shuffle#3:	deck: (0 8 7 6 5 4 3 2 1 9)
shuffle#4:	deck: (0 4 8 3 7 2 6 1 5 9)
shuffle#5:	deck: (0 2 4 6 8 1 3 5 7 9)
(0 1 2 3 4 5 6 7 8 9)
shuffle#0:	deck: (0 1 2 3 4 5 6 7 8 9 10 11 12 13)
shuffle#1:	deck: (0 7 1 8 2 9 3 10 4 11 5 12 6 13)
shuffle#2:	deck: (0 10 7 4 1 11 8 5 2 12 9 6 3 13)
shuffle#3:	deck: (0 5 10 2 7 12 4 9 1 6 11 3 8 13)
shuffle#4:	deck: (0 9 5 1 10 6 2 11 7 3 12 8 4 13)
shuffle#5:	deck: (0 11 9 7 5 3 1 12 10 8 6 4 2 13)
shuffle#6:	deck: (0 12 11 10 9 8 7 6 5 4 3 2 1 13)
shuffle#7:	deck: (0 6 12 5 11 4 10 3 9 2 8 1 7 13)
shuffle#8:	deck: (0 3 6 9 12 2 5 8 11 1 4 7 10 13)
shuffle#9:	deck: (0 8 3 11 6 1 9 4 12 7 2 10 5 13)
shuffle#10:	deck: (0 4 8 12 3 7 11 2 6 10 1 5 9 13)
shuffle#11:	deck: (0 2 4 6 8 10 12 1 3 5 7 9 11 13)
(0 1 2 3 4 5 6 7 8 9 10 11 12 13)
(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 8 52 20 18 58 60 6 12 66 22 35 9 20 30 39 54 82 8 28 11 12 10 36 48 30 ... 9900 660 564 9906 1098 520 473 660 4830 36 3306 9922 220 174 292 3310 210 3972 522 828 9940 1620 24 588 9948 530 2412 180 3318 792 237 1620 996 4983 3322 4524 3324 180 4530 2344 3324 4884 1996 1664 4278 816 222 1332 384 300)
2 tests passed