Perfect shuffle
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
<lang lisp>
- 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:
<lang J> shuf=: /: $ /:@$ 0 1"_</lang>
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> (50*i.100) shuflen ::_:@+/ (#~ 0=2&|)i.50
_ 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
<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 1st 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 1st 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