Fifty Shades of J/Chapter 31
Table of Contents ... Glossary ... Previous Chapter ... Next Chapter
Principal Topics
- /: (grade up) ^: (power conjunction) ripple shuffles
A ‘ripple shuffle’ of a deck of cards consists of dividing it into two halves (or as nearly as possible if there is an odd number). How many shuffles will it take for a deck of, say, 52 cards to return to its original state?
Suppose the cards are numbered consecutively from 0, and that there is an even number of cards. Then if all the even-numbered cards are placed in order on top of all the odd-numbered ones, a ripple shuffle would restore the original order. To put this in another way, a ripple shuffle is the inverse of ‘all evens first’ sort. Dyadic grade up performs by sorting its left argument to an order specified by its right argument, so if the latter is a list of alternating 0s and 1s of the same length as the former the effect is to obtain all the items of one parity followed by all the items of the other.
irs=:/: 0 1&($~)@# irs 'abcdef' acebdf
Use the power conjunction to do this repeatedly
irs^:(i.7)i.10 NB. 7 inverse shuffles 0 1 2 3 4 5 6 7 8 9 0 2 4 6 8 1 3 5 7 9 0 4 8 3 7 2 6 1 5 9 0 8 7 6 5 4 3 2 1 9 0 7 5 3 1 8 6 4 2 9 0 5 1 6 2 7 3 8 4 9 0 1 2 3 4 5 6 7 8 9
Once the original order is restored, a succession of ripple shuffles is obtained by reading the rows of the above table from bottom to top. To count the number of shuffles required to restore the original order, the direction in which the table is read is immaterial, so define :
countrs=:monad :0 r=.y [ i=.1 while. -.y-:irs r do. r=.irs r [ i=.>:i end. i ) countrs i.10 6
For a deck of 52 cards the number of ripple shuffles required to restore the original order is
countrs i.52 8
A range of even card numbers can be explored some of whose results may be a little surprising at first sight :
w,:>countrs each i. each w=.2+2*i.20 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 1 2 4 3 6 10 12 4 8 18 6 11 20 18 28 5 10 12 36 12 w,:>countrs each i. each w=.22+2*i.20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 6 11 20 18 28 5 10 12 36 12 20 14 12 23 21 8 52 20 18 58 w,:>countrs each i. each w=.64+4*i.15 64 68 72 76 80 84 88 92 96 100 104 108 112 116 120 6 66 35 20 39 82 28 12 36 30 51 106 36 44 24
Intuitively it might be expected that numbers which are relatively rich in factors would have relatively short run lengths, however this is not in general the case. For example compare 60 with 92,
A variation on the ripple shuffle is to do a final exchange of the two half-decks by changing 0 1 to 1 0 in the verb irs and changing irs correspondingly in countrs. The results for the first few values are
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 2 4 3 6 10 12 4 8 18 6 11 20 18 28 5 10 12 36 12 20
The row above is the same as that of the corresponding row in the previous table, only shifted one place to the left. Thus if rs(n) is the run length for a pack of n cards without final half-deck exchange, and rss(n) is the run length with exchange, then rss(n)=rs(n+ 2).
Apart from the powers of two for which rs(n) is simply log2n, the pattern of rs(n) is an irregular one with some abrupt changes. In general low values of rs(n) and rss(n) go together, although this is not always the case, e.g. rs(54)=rss(52)=52, that is the effect of the seemingly final switch of the two half-decks for a 52-card deck is that 52 runs rather than 8 are required for restoration.
Another way to address the problem of order-restoring shuffle run lengths is to observe the position of, say, the number 1 in successive shuffles in the table above, remembering to read it upwards!. Its successive positions are 1, 2, 4, 8, then it wraps round to position 7 which = 16 in modulo 9 arithmetic. Then look at the progress of the number 2, which moves to position 4, 8, 7, 5, or 4, 8, 16, 32 in modulo 9 arithmetic. Thus the numbers 1 and 2 will be restored in the same number of shuffles, and similarly for all the other numbers.
The problem of counting the number of shuffles needed to restore the original order is thus equivalent to that of obtaining a second 1 in the sequence 2^i.10 in modulo 9 arithmetic, thus
9|2^i.13 1 2 4 8 7 5 1 2 4 8 7 5 1
shows the 6-cycle already observed with 10 cards. Since the number of shuffles to restore in general cannot exceed the number of cards, the number of shuffles comes from observing 1s in (n-1)|2&^@>:@i.(n+1), leading to
(<:|2&^@>:@i.)10 2 4 8 7 5 1 2 4 8 7
following which the number of shuffles for various cases is given by
v=:2&^@>:@i. count=:>:@i.&1@(<:|v) count 10 6 w,:>count each w=.12+2*i.15 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 10 12 4 8 18 6 11 20 18 28 5 10 12 36 12 w,:>count each w=.44+4*i.15 44 48 52 56 60 64 68 72 76 80 84 88 92 96 100 14 23 8 20 61 6 69 35 20 39 85 28 12 36 30
A few of these values such as that for 60 are inconsistent with the previous table. This is because 260 is rather a large number which requires extended precision for exact integer comparison. Thus in the event of discrepancy it is counts which delivers the correct values
To deal with the variation in which the two half-decks are exchanged at the end of the shuffle, simply replace the <: in the middle with >:
counts=:>:@i.&1@(>:|v) counts 10 10
Here is a graph of rs(n) from n=2 to n=120
As noted earlier, the powers of 2 are easy to deal with, they are simply log2n. But why do 22, 52, 74 an 92 have short cycles whereas 20, 30, 50 and 60 have long ones? And why are there regions of relatively short run lengths such as between 86 and 100? Any suggestions?
Code Summary
irs=:/: 0 1&($~)@# NB.sorts list, odd-indexed items, then even countrs=:monad :0 NB.exact count of sorts to restoration r=.y [ i=.1 while. -.y-:irs r do. r=.irs r [ i=.>:i end. i ) v=:2&^@>:@i. NB. powers of 2 from 1 to y count=:>:@i.&1@(<:|v) NB. count to restoration for n<60 counts=:>:@i.&1@(>:|v) NB. ditto with half-list switching