Perfect shuffle: Difference between revisions

From Rosetta Code
Content added Content deleted
(→‎{{header|REXX}}: added the REXX language.)
(Added Ruby)
Line 237: Line 237:


(elided)
(elided)
</pre>

=={{header|Ruby}}==
<lang ruby>def perfect_shuffle(n)
start = *1..n
deck = start.dup
m = n / 2
magic_shuffle = ->(d){ d.shift(m).zip(d).flatten }
1.step do |i|
deck = magic_shuffle[deck]
return i if deck == start
end
end

fmt = "%4d -%5d :" + "%5d" * 20
(2..10000).step(2).each_slice(20) do |ary|
puts fmt % [*ary.minmax, *ary.map{|n| perfect_shuffle(n)}]
end</lang>

{{out}}
<pre>
2 - 40 : 1 2 4 3 6 10 12 4 8 18 6 11 20 18 28 5 10 12 36 12
42 - 80 : 20 14 12 23 21 8 52 20 18 58 60 6 12 66 22 35 9 20 30 39
82 - 120 : 54 82 8 28 11 12 10 36 48 30 100 51 12 106 36 36 28 44 12 24
122 - 160 : 110 20 100 7 14 130 18 36 68 138 46 60 28 42 148 15 24 20 52 52
162 - 200 : 33 162 20 83 156 18 172 60 58 178 180 60 36 40 18 95 96 12 196 99
202 - 240 : 66 84 20 66 90 210 70 28 15 18 24 37 60 226 76 30 29 92 78 119
242 - 280 : 24 162 84 36 82 50 110 8 16 36 84 131 52 22 268 135 12 20 92 30
282 - 320 : 70 94 36 60 136 48 292 116 90 132 42 100 60 102 102 155 156 12 316 140
322 - 360 : 106 72 60 36 69 30 36 132 21 28 10 147 44 346 348 36 88 140 24 179
362 - 400 : 342 110 36 183 60 156 372 100 84 378 14 191 60 42 388 88 130 156 44 18
402 - 440 : 200 60 108 180 204 68 174 164 138 418 420 138 40 60 60 43 72 28 198 73
442 - 480 : 42 442 44 148 224 20 30 12 76 72 460 231 20 466 66 52 70 180 156 239
482 - 520 : 36 66 48 243 162 490 56 60 105 166 166 251 100 156 508 9 18 204 230 172
522 - 560 : 260 522 60 40 253 174 60 212 178 210 540 180 36 546 60 252 39 36 556 84
562 - 600 : 40 562 28 54 284 114 190 220 144 96 246 260 12 586 90 196 148 24 198 299
.
.
.
9602 - 9640 : 2400 240 56 492 3202 4116 9612 64 4698 9618 1068 283 300 1604 9628 1605 468 460 418 216
9642 - 9680 : 155 9642 428 4380 402 804 588 3860 252 4452 9660 644 644 1380 1460 4572 568 420 9676 4839
9682 - 9720 : 1380 4620 444 1076 4844 110 3222 276 2424 780 396 780 1292 456 18 492 4410 924 780 43
9722 - 9760 : 810 462 1940 2380 1518 4716 9732 580 636 3246 760 4871 1948 342 9748 693 650 3900 4430 3252
9762 - 9800 : 1582 1500 60 4883 1221 814 84 440 1086 210 652 1086 612 3262 300 4895 699 652 1200 2380
9802 - 9840 : 2970 9802 468 1398 144 3270 1090 60 1636 3270 660 2070 260 1580 1404 28 4916 420 1092 4919
9842 - 9880 : 756 96 1780 532 462 9850 4814 36 4928 9858 1548 2112 1972 660 4830 4935 822 3900 984 396
9882 - 9920 : 120 9882 1316 4943 140 156 1140 3956 3298 2340 9900 660 564 9906 1098 520 473 660 4830 36
9922 - 9960 : 3306 9922 220 174 292 3310 210 3972 522 828 9940 1620 24 588 9948 530 2412 180 3318 792
9962 -10000 : 237 1620 996 4983 3322 4524 3324 180 4530 2344 3324 4884 1996 1664 4278 816 222 1332 384 300
</pre>
</pre>

Revision as of 14:22, 3 May 2015

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

REXX

<lang rexx>/*REXX program shows a generalized FizzBuzz pgm: #1 name1 #2 name2 ···*/ parse arg n . /*get optional args from the C.L.*/ if n== then n=20000 /*N not set? Then use default.*/ w=length(n) /*W: used for formatting numbers.*/ 

           do i=2  to N  by 2         /*create the "decks" to be used. */
           bef=gen(i)                 /*generate a deck  (of numbers). */
                                      /* [↑]  keep shuffling 'til done.*/
              do t=1 until aft==bef   /*shuffling 'til  after = before.*/
              aft=pShuffle(I)         /*do perfect shuffle, set string.*/
              end   /*t*/

           say 'deck size='right(i,w)     "  perfect shuffles="right(t,w)
           end   /*i*/

exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────PSHUFFLE subroutine─────────────────*/ pShuffle: parse arg x; z=0 /*get argument, set the Z pointer*/ h=x%2 /*get the half-way (midpoint) ptr*/ 

        do s=1  for x%2; z=z+1; h=h+1 /*traipse through the "deck" pips*/
        !.z=@.s;         z=z+1        /*set the left half; bump pointer*/
        !.z=@.h                       /* "   " right   "               */
        end   /*s*/                   /*perform perfect shuffle of deck*/

a= /*init. A to null.*/ 

        do r=1  for x;  @.r=!.r;  a=a @.r;  end   /*assign to a string.*/

return a /*return "after" str.*/ /*──────────────────────────────────GEN subroutine──────────────────────*/ gen: parse arg x; _=; do y=1 for x; @.y=y; _=_ y; end; return _</lang> output (abbreviated) when using the default input: 

deck size= 2   perfect shuffles= 1
deck size= 4   perfect shuffles= 2
deck size= 6   perfect shuffles= 4
deck size= 8   perfect shuffles= 3
deck size=10   perfect shuffles= 6
deck size=12   perfect shuffles=10
deck size=14   perfect shuffles=12
deck size=16   perfect shuffles= 4
deck size=18   perfect shuffles= 8
deck size=20   perfect shuffles=18
deck size=22   perfect shuffles= 6
deck size=24   perfect shuffles=11
deck size=26   perfect shuffles=20
deck size=28   perfect shuffles=18
deck size=30   perfect shuffles=28
deck size=32   perfect shuffles= 5
deck size=34   perfect shuffles=10
deck size=36   perfect shuffles=12
deck size=38   perfect shuffles=36
deck size=40   perfect shuffles=12
 ∙
 ∙
 ∙

(elided)

Ruby

<lang ruby>def perfect_shuffle(n) 

 start = *1..n
 deck = start.dup
 m = n / 2
 magic_shuffle = ->(d){ d.shift(m).zip(d).flatten }
 1.step do |i|
   deck = magic_shuffle[deck]
   return i if deck == start
 end

end

fmt = "%4d -%5d :" + "%5d" * 20 (2..10000).step(2).each_slice(20) do |ary| 

 puts fmt % [*ary.minmax, *ary.map{|n| perfect_shuffle(n)}]

end</lang>

Output:
   2 -   40 :    1    2    4    3    6   10   12    4    8   18    6   11   20   18   28    5   10   12   36   12
  42 -   80 :   20   14   12   23   21    8   52   20   18   58   60    6   12   66   22   35    9   20   30   39
  82 -  120 :   54   82    8   28   11   12   10   36   48   30  100   51   12  106   36   36   28   44   12   24
 122 -  160 :  110   20  100    7   14  130   18   36   68  138   46   60   28   42  148   15   24   20   52   52
 162 -  200 :   33  162   20   83  156   18  172   60   58  178  180   60   36   40   18   95   96   12  196   99
 202 -  240 :   66   84   20   66   90  210   70   28   15   18   24   37   60  226   76   30   29   92   78  119
 242 -  280 :   24  162   84   36   82   50  110    8   16   36   84  131   52   22  268  135   12   20   92   30
 282 -  320 :   70   94   36   60  136   48  292  116   90  132   42  100   60  102  102  155  156   12  316  140
 322 -  360 :  106   72   60   36   69   30   36  132   21   28   10  147   44  346  348   36   88  140   24  179
 362 -  400 :  342  110   36  183   60  156  372  100   84  378   14  191   60   42  388   88  130  156   44   18
 402 -  440 :  200   60  108  180  204   68  174  164  138  418  420  138   40   60   60   43   72   28  198   73
 442 -  480 :   42  442   44  148  224   20   30   12   76   72  460  231   20  466   66   52   70  180  156  239
 482 -  520 :   36   66   48  243  162  490   56   60  105  166  166  251  100  156  508    9   18  204  230  172
 522 -  560 :  260  522   60   40  253  174   60  212  178  210  540  180   36  546   60  252   39   36  556   84
 562 -  600 :   40  562   28   54  284  114  190  220  144   96  246  260   12  586   90  196  148   24  198  299
  .
  .
  .
9602 - 9640 : 2400  240   56  492 3202 4116 9612   64 4698 9618 1068  283  300 1604 9628 1605  468  460  418  216
9642 - 9680 :  155 9642  428 4380  402  804  588 3860  252 4452 9660  644  644 1380 1460 4572  568  420 9676 4839
9682 - 9720 : 1380 4620  444 1076 4844  110 3222  276 2424  780  396  780 1292  456   18  492 4410  924  780   43
9722 - 9760 :  810  462 1940 2380 1518 4716 9732  580  636 3246  760 4871 1948  342 9748  693  650 3900 4430 3252
9762 - 9800 : 1582 1500   60 4883 1221  814   84  440 1086  210  652 1086  612 3262  300 4895  699  652 1200 2380
9802 - 9840 : 2970 9802  468 1398  144 3270 1090   60 1636 3270  660 2070  260 1580 1404   28 4916  420 1092 4919
9842 - 9880 :  756   96 1780  532  462 9850 4814   36 4928 9858 1548 2112 1972  660 4830 4935  822 3900  984  396
9882 - 9920 :  120 9882 1316 4943  140  156 1140 3956 3298 2340 9900  660  564 9906 1098  520  473  660 4830   36
9922 - 9960 : 3306 9922  220  174  292 3310  210 3972  522  828 9940 1620   24  588 9948  530 2412  180 3318  792
9962 -10000 :  237 1620  996 4983 3322 4524 3324  180 4530 2344 3324 4884 1996 1664 4278  816  222 1332  384  300
Retrieved from "https://rosettacode.org/wiki/Perfect_shuffle?oldid=256528"