Perfect shuffle: Difference between revisions

Content added Content deleted

Inline

Revision as of 20:15, 15 June 2015

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

EchoLisp

shuffler

a permutation vector which interleaves both halves of deck

(define (make-shuffler n) (let ((s (make-vector n))) (for ((i (in-range 0 n 2))) (vector-set! s i (/ i 2))) (for ((i (in-range 0 n 2))) (vector-set! s (1+ i) (+ (/ n 2) (vector-ref s i)))) s))

output

(n . # of shuffles needed to go back)

(define (magic-shuffle n) (when (odd? n) (error "magic-shuffle:odd input" n)) (let [(deck (list->vector (iota n))) ;; (0 1 ... n-1) (dock (list->vector (iota n))) ;; keep trace or init deck (shuffler (make-shuffler n))]

(cons n (1+ (for/sum ((i Infinity)) ; (in-naturals missing in EchoLisp v2.9) (vector-permute! deck shuffler) ;; permutes in place #:break (eqv? deck dock) ;; compare to first 1))))) </lang>

Output:

For reasons of size ... and performance for large n, we compute the results by chuncks of 50. The result format is: (deck size . number of steps to go back) <lang lisp> (make-shuffler 10) → #( 0 5 1 6 2 7 3 8 4 9) ;; sample permutation vector for n = 10

(map magic-shuffle (range 2 102 2)) ;; 40 msec

→ ((2 . 1) (4 . 2) (6 . 4) (8 . 3) (10 . 6) (12 . 10) (14 . 12) (16 . 4) (18 . 8) (20 . 18) (22 . 6) (24 . 11) (26 . 20) (28 . 18) (30 . 28) (32 . 5) (34 . 10) (36 . 12) (38 . 36) (40 . 12) (42 . 20) (44 . 14) (46 . 12) (48 . 23) (50 . 21)

(52 . 8) (54 . 52) (56 . 20) (58 . 18) (60 . 58) (62 . 60) (64 . 6) (66 . 12) (68 . 66) (70 . 22) (72 . 35) (74 . 9) (76 . 20) (78 . 30) (80 . 39) (82 . 54) (84 . 82) (86 . 8) (88 . 28) (90 . 11) (92 . 12) (94 . 10) (96 . 36) (98 . 48) (100 . 30))

(map magic-shuffle (range 9900 10002 2)) ;; 9 seconds → ((9900 . 2340) (9902 . 9900) (9904 . 660) (9906 . 564) (9908 . 9906) (9910 . 1098) (9912 . 520) (9914 . 473) (9916 . 660) (9918 . 4830) (9920 . 36) (9922 . 3306) (9924 . 9922) (9926 . 220) (9928 . 174) (9930 . 292) (9932 . 3310) (9934 . 210) (9936 . 3972) (9938 . 522) (9940 . 828) (9942 . 9940) (9944 . 1620) (9946 . 24) (9948 . 588) (9950 . 9948) (9952 . 530) (9954 . 2412) (9956 . 180) (9958 . 3318) (9960 . 792) (9962 . 237) (9964 . 1620) (9966 . 996) (9968 . 4983) (9970 . 3322) (9972 . 4524) (9974 . 3324) (9976 . 180) (9978 . 4530) (9980 . 2344) (9982 . 3324) (9984 . 4884) (9986 . 1996) (9988 . 1664) (9990 . 4278) (9992 . 816) (9994 . 222) (9996 . 1332) (9998 . 384) (10000 . 300))

Let's look in the On-line Encyclopedia of Integer Sequences Given a list of numbers, the (oeis ...) function looks for a sequence

(lib 'web) Lib: web.lib loaded. (oeis '(1 2 4 3 6 10 12 4)) → Sequence A002326 found </lang>

J

The shuffle routine:

Example uses:

<lang J> shuf 'abcdef' adbecf

  shuf 'abcdefgh'

aebfcgdh</lang>

The cycle length routine:

<lang J> shuflen=: [: *./ #@>@C.@shuf@i.</lang>

The task example (with most of the middle trimmed out to avoid crashing the rosettacode wiki implementation):

<lang J> shuflen"0 }.2*i.5000 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 ... 4278 816 222 1332 384</lang>

Here's a representation of what all but the very last value (which is 384):

<lang J> (1000*i.5) shuflen ::_:@+/ (#~ 0=2&|)i.1000

  _    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 110   20  100    7  14  130   18   36   68  138   46   60  28  42  148  15   24  20   52   52   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   92   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  102  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  164  138  418 420  138  40   60   60  43   72   28  198   73   42 442  44  148  224   20   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  196  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  660   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  244   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   90  419  812   70 156  330   94  396  852  36  428 858   60  431 172  136 390 132   48  300  876  292  55 882 116  443   21  270  414 356  132  140  104   42 180  906  300   91  410   60  390  153  102  420 180  102  464  126  310   40  117  156  940  220  36  946   36  316   68  380  140  204 155  318  96  483   72  194  138   60 488  110  36 491 196  138  154 495   30  396  332
 36   60  232 132  468 504   42   92  84  84 1018  340   10  20  156  294  515 258  132  120  519  346  444 180 348 262 350  108 420   15  88 1060  531 140  240  356   24  252  140 358  492  253  342  60  543 330 1090  364   36 274  156  366   29  24  180 1108  100 156  148 1116  372 522 1122  300  231 564   84  510  452  378  264  162   42  76 180  382 575  288  60  132  180  126  166 116  388  249 1170   88  460 530 390  236  156 156 1186  140  44 298  476   18 180 300  200  24  280   60 516 1212 324  152  572  180  611 420  204 1228  615 204   36 1236  174   72  140 164  28 156 138  534 100 418 1258   48 420 220  180  414  20  198  40 1276  639   60 1282  16   60  161 1290   86   36  648   72 1300 651  84 1306  120  198  300  524  146  659   60  126 260  221  442 1210   70  44  285  204  444 312 268  224  630   96   20 540  638   30 680  644  12 683 1332   76 1372  100  216 588 1380 460  92   18  462  636   99  60   70  233  466 660 140   66 704 328  156  188   36   70  84  237 180 1426   84 468  179   60  478  719  130  36 136  723   66 1450 1452  48  115  486  486   90 292  162   84  245 490  580  210   56  370 1482 180  743  744  210 1492 132  166 1498  234  498  84  340  502  755   88  100  180 105  156 1522  60  508 690 1530   18  204  364   54   66  771 204   24 1548  230 194 620  516  779  111  260 156 783  522 1570 660   60 738  526   40  791 316 506 678  252  522  140  532   60 400  228 212  803  201 534   52   72  210 1618 1620  540 300  542  180  87  385  36 1636  740 546  260  276  180   48   84 252  60  92   78   30  831  36 1666 1668  556  357  660   84   99 820  120  84   24 562  198 1692  28  848  566  162  780  20  284  244  812  114  588 200  570  215  574 220  260   36 144 1732  692  96  828 1740  246 348 1746  260 408  146   36  150 879  586  140  88   90  420  330  588 140   74  148 204  891  24 1786  596 198  810 716  598   48   25   50 684  276  198 362  252  220  429  424  606 911 180  84 290  305  276  732  830  612  393  144  60  923  602  154   72 156  618 780 1860  594 372 1866  66 935  936  500 1876  939  90 804  84   72  472   60   90 756  135  210 1900  860  28 1906  902   84  239  764  630  900   56   64  60  460  214 1930  644   84  444  276  646  924 388  290 1948  975   30   88  306  652 468   60 260  210  890   18 1972  780 658 1978 282 660  44 1986   24 180  996   36 1996
333  308  286 200  222 420  402   60  60 336   48  322  408 540 2026 2028  676 954  180   48 1019  156  678 204  11  22 876 2052  68  440 140  228 1031 348  156 2068   36  230  820 330   90 1040 2082 276 1043  29   40  132  836 174 2098  190  700 420   42   36 1055  44  276  252  324 300  480  200  708 532 2130  234   60 1068  110 2140   51  60 252  102 714 1076 172  718   56 1080  102  72  980   24  996  260  140 465 726  242 1044 396 1458  990 156  56  292 2028 244  35  734  84 1103 1081 330 2212 884  246  948 2220   36 220  520  742  528 420  148 2236 1119  738 2242 224 318 516 750  750  20 180  150   72  45  60 2266 2268 756  568  60  330  364  190  380  76  381   36 1092 2292   72 1148  990  348 483 460  384 2308 1155   48  924   30  772  210 1100  20 1068  136   36 2332 932  180 2338  780  70 132  782  756   47  180  52 2356   21 786  552 140 786  561 2370   84  900 1188  60  476 397 156   30 2388  796  598 956  184 1199 1029 198  36 1148  90 482  126  132 1208  580 804 1211 240  404 1038 120  270  972 2436  270  305 348 324 1223  195  126  370 980   36 2458 1166  820  56 2466  822  264 618   60 2476  396  826 1140 420  828 1170 1196  276 332 1130  168   60 1251 332  396   96  270  537 1004  838 380 1260  812 100  342 210 2530  296  156  406 2538  330 1271 508  282 2548 1275 396  36 2556  852  588  290  36 120  183  428 410 1020 858 2578  308   60 460 396 862 1295   81  172 1092  308 408  612 260  390 1304 372  132 1044 1308  144 2620  420 300 1260 1190 876 1316  40  876   84 414  110 1012 1323  882  120 378 348 166 2658  886 1331  60   42  104  445  810 1060 2676  414 573 2682 356   79 224  132 2692 420  140 2698   36  104 540 2706   42 1355 1356  180 180 1359  906 1164 180  900 1364  26  182 1092 264  410 2740  420  60  660  916 390 1376  252  306  55   50  102 156  461  420  648 1334 180 1388  132 306  110 556  464 2788 465  126  84 2796  930 1400 2802  40  600 2756 234  336 1124  156 2818   60 940 140  80 220 1332  118  108 2836  664  946 2842 284   36  180 2850  948 228  102  68 2860  204 380 1380  90 420  312 1100  204 1439 462 310 144 1443  954 1218 1310  96 1448  444  966 1451 492   72 2908  140  194  260  972  138   77  468  60 1463  700  488 1254 1172  110 2938  344   36 180  420  982 1356  492  196 2956 1340 138 2962 148  154  371  110  990  120 228   30 270 468 396 1428  420 332  180 1196  108

1499 1500 60 100 240 232 3010 1430 132 129 3018 468 1511 220 504 348 72 42 1212 3036 92 1520 712 84 460 762 252 70 276 1018 198 204 340 612 3066 30 1476 219 20 360 1539 156 3082 308 294 772 70 1030 1236 162 258 1326 1484 396 1428 444 120 470 132 1038 1559 156 1038 2500 1508 444 100 24 180 784 126 348 672 72 262 1518 748 350 180 60 324 252 1054 420 1583 1584 30 1494 140 264 680 1060 1060 84 3186 1062 55 255 420 1518 228 240 3202 64 356 1604 468 72 428 804 252 644 1460 140 1380 1076 1074 780 1292 492 780 231 506 580 760 342 650 3252 60 407 1086 1086 300 652 990 1398 545 1090 260 28 364 96 462 36 1548 660 274 396 1316 156 3298 660 366 660 3306 58 210 828 24 530 1659 540 3322 180 1108 1664 222 100 308 805 156 48 557 148 3346 392 1116 717 60 372 1679 168 522 48 36 1122 3370 1124 900 510 180 462 792 676 564 484 113 84 48 546 510 1602 820 452 1703 243 378 3412 44 264 1572 310 162 340 1628 126 207 1716 76 1470 180 180 780 156 1146 431 168 1150 460 576 288 3460 577 60 3466 3468 132 165 1380 180 105 3422 378 40 1580 166 3490 498 116 804 3498 1164 140 700 498 1540 1755 1170 36 3516 264 753 540 460 1763 882 530 3532 300 1170 3538 236 236 708 3546 156 1716 360 156 3556 1779 1186 1524 220 140 574 3570 132 60 63 298 3580 1791 476 840 144 18 1796 1436 180 1740 276 300 204 601 600 572 3612 24 1808 690 280 1811 700 60 1710 605 516 484 3636 1212 30 3642 972 780 220 152 420 56 572 3658 522 180 244 288 1222 1835 918 420 3676 564 204 28 660 1228 120 3690 1230 492 1848 612 3700 759 36 210 3708 1236 897 1484 174 1859 3660 72 740 1863 140 60 3732 492 900 534 28 1764 636 156 1782 110 414 1500 408 534 188 1820 100 1883 1884 1254 1470 60 1258 3778 198 48 756 540 420 296 1896 220 3796 1820 180 3802 380 1242 876 612 20 36 1730 198 764 637 120 154 546 1276 958 348 1278 1740 913 60 384 1923 1282 3850 3852 16 252 904 180 1931 772 322 468 273 1290 100 3876 258 388 440 36 1716 648 648 152 180 72 1668 1886 1300 140 3906 1302 1955 84 252 3916 1959 1306 3922 260 120 1964 3930 198 1572 35 300 1686 219 524 3946 1790 438 1914 84 1318 1908 232 60 60 1983 378 1710 476 260 240 1892 442 852 796 1326 3988 204 1210 184 114

 70 1000 4002 132 2003 630  570 4012 180 204 4018 4020 1332 660 1342  312 1932  36  268 1830  144  672 1860 404 630 506  50   96 540  169  60  130  952 540 1722  156  638 2036 1620  90 2039  780  680 252  660 644 4090 4092   12  24 4098 1366 1860 820 1332 1758 2055 228 1644 1958 1372 948   90  100 2063 688  648 4132 1652  588 4138  100 1380 828 420 1380 444  346  92 4156 2079   18 1980 168  462 1890  336  636 1660  87 198  252  253 180  156 2030  70 897 1676  466  72 525 1398 812   75  660 842 1910 140 1054 4218   66 1020 780  704 4228 2115 328  660  666  468 2120 4242 188 340 303  36 4252 396 210 4258 4260  84 852  200  474 305  534 180  276 1940 1426 4282 428   84 1072  612 1404 1716  537  358  440  60  60  522  690 1434 2034 1724 1438  462 1036  130 860 2163   36  420  618 136 2168 1446 1446 700 780  198 4348  684 1450 132 4356 1452 231 4362  48 220   16  230 4372 1500  486 420   84 486 876 1060   90 2195 1045 292 4396 2132  162  72 220   84 551 200  490 1764   45 1470 340  737 580  522  714 210   60 1772  168 1056 2220 370  84 2223 1482 4450  180 540 1114  588 1486 2231 828  744  180 1048 210 1780 1980 1492  560 4482 132  192 4422  498 4492 140 1498 1020  642  234 104 4506 1494 2076   47   84 4516 753  340  266 180 1506 969 2156 1510 1812  348   88 2142  870 300 4546 1516  180 364 364  210 1104 2280  468 820 761 1522 1956 536   60  99   72 1524 2291 780 690 264 2295 1530  612 1532   18 742 4602 204 1080 2090 364 1974  420  162  740 4620   66 900  660 1542 420  140 204 4636 2319  24  422  464 1548 2324 1550 690 252 388  194 2262  777 620 2148  924 1548 2336   40 1558 2339  15  222 468  252 780 4690  684 156   60  252 1566 2351 940  522  184   48 1570  220 572  660  295 4722 180 2268  788 738  364 1892 526 2028  430  120  36 2300 1582 475  336  316 2310 793 1518  360  68  678  450  732  252 380  280 1566  66 2391 140 4786 4788 532 2396 204   60 2399 1200  400 620  990  228 376 4812  636 1204  780 1606 156 480 402 730 2415 1602 1932  690   52 1173 2324  72 2340  372  210 2310 388 1618  28  972 1620 276  260 540 487 2210  300 4876  120 542 144 488  180 2444  198  174 220 2378  770 1092 2451  36 2100 1636 1636 2312 1964  740 2459   36  546 980  756  260  986 4932  276 1234 1120  540 2471 308   48 2100 2475   84 1980 4956  252 220  708  60 2483 2484   92 4972 1980  78 2292 584  30 332 4986 1662 165  624   36 2358</lang>

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

Perl

<lang perl>use List::Util qw(all);

sub perfect_shuffle {

  my $mid = @_ / 2;
  map { @_[$_, $_ + $mid] } 0..($mid - 1);

}

for my $i (2 .. 10000) {

   next if $i % 2;
   
   my $n = 0;
   my @shuffled = my @deck = 1 .. $i;
   do {
       $n++;
       @shuffled = perfect_shuffle(@shuffled);
   } until all { $shuffled[$_] == $deck[$_] } 0..$#shuffled;
   
   printf "%5d ", $n;
   print "\n" if !($i % 20)

}</lang>

Output:

    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 
  110    20   100     7    14   130    18    36    68   138
(...elided...)

Perl 6

Translation of: Perl

<lang perl6>sub perfect-shuffle (@deck) {

  my $mid = @deck / 2;
  flat @deck[0 .. $mid-1] Z @deck[$mid .. *-1];

}

for 2, 4 ... 10000 -> $i {

   my @shuffled = my @deck = 1 .. $i;
   
   my $n;
   loop {
       $n++;
       @shuffled = perfect-shuffle @shuffled;
       last if @shuffled eqv @deck;
   }
   
   printf "%5d ", $n;
   print "\n" if $i %% 20;

}</lang>

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

unoptimized

<lang rexx>/*REXX program does a "perfect shuffle" for a number of even numbered decks.*/ parse arg N .; if N== then n=10000 /*N not specified? Then use default.*/ w=length(N) /*used for right─aligning the numbers. */

   do j=2  to N  by 2                 /*create some even-numbered card decks.*/

     do k=1  for j;       @.k=k;       end       /*generate a deck to be used*/
     do t=1  until eq();  call magic;  end       /*shuffle 'til before=after.*/

   say 'deck size:'    right(j,w)","       right(t,w)      'perfect shuffles.'
   end   /*j*/

exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────EQ subroutine─────────────────────────────*/ eq: do ?=1 for j; if @.?\==? then return 0; end; return 1 /*──────────────────────────────────MAGIC subroutine──────────────────────────*/ magic: z=0 /*set the Z pointer (used as index).*/ h=j%2 /*get the half─way (midpoint) pointer. */

      do s=1  for h;  z=z+1;  h=h+1   /*traipse through the card deck pips.  */
      !.z=@.s;        z=z+1           /*assign left half; then bump pointer. */
      !.z=@.h                         /*   "   right  "                      */
      end   /*s*/                     /*perform a perfect shuffle of the deck*/

      do r=1  for j;  @.r=!.r;  end   /*re─assign to the original card deck. */

return</lang> output (abbreviated) when using the default input:

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

(the rest of the output was elided.)

optimized

This REXX version takes advantage that the 1^st and last cards of the deck don't change. <lang rexx>/*REXX program does a "perfect shuffle" for a number of even numbered decks.*/ parse arg N .; if N== then n=10000 /*N not specified? Then use default.*/ w=length(N) /*used for right─aligning the numbers. */

   do j=2  to N  by 2                 /*create some even-numbered card decks.*/

     do k=1  for j;       @.k=k;       end       /*generate a deck to be used*/
     do t=1  until eq();  call magic;  end       /*shuffle 'til before=after.*/

   say 'deck size:'    right(j,w)","       right(t,w)      'perfect shuffles.'
   end     /*j*/

exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────EQ subroutine─────────────────────────────*/ eq: do ?=1 for j; if @.?\==? then return 0; end; return 1 /*──────────────────────────────────MAGIC subroutine──────────────────────────*/ magic: z=1; h=j%2; m=h-1 /*set Z & H (half─way) pointers.*/

 do L=3  by 2  for m;  z=z+1;  !.L=@.z; end  /*assign left half of the deck. */
 do R=2  by 2  for m;  h=h+1;  !.R=@.h; end  /*   "   right  "   "  "    "   */
 do a=2        for j-2;        @.a=!.a; end  /*re─assign to the original deck*/

return</lang> output is the same as the 1^st version.

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