Perfect Shuffles in J
Vector 13:2, page 108
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 108
The following problem was presented in [0]:
Magicians often perform amazing card tricks based on skilful execution of a "perfect shuffle". A perfect shuffle divides a deck of cards into two halves and interweaves them by alternating one card at a time from each half deck.
Here we will similarly shuffle alphabetic letters. For example, suppose the letters ‘TECHNOLOGY’ are written separately on index cards and stacked into a deck. Now divide the deck into halves and shuffle the cards — perfectly. The new deck spells ‘TOELCOHGNY’. Further, we ask: if this deck were shuffled perfectly again, repeatedly, what spellings would result? The sequence below may be surprising.
‘TECHN’ shuffle ‘OLOGY’ yields ‘TOELCOHGNY’
‘TOELC’ shuffle ‘OHGNY’ yields ‘TOOHEGLNCY’
‘TOOHE’ shuffle ‘GLNCY’ yields ‘TGOLONHCEY’
‘TGOLO’ shuffle ‘NHCEY’ yields ‘TNGHOCLEOY’
‘TNGHO’ shuffle ‘CLEOY’ yields ‘TCNLGEHOOY’
‘TCNLG’ shuffle ‘EHOOY’ yields ‘TECHNOLOGY’
After six perfect shuffles, the original word is reproduced! This occurs similarly for other words.
The problem for you to program (in a language of your choice) is posed at three levels:
1.1 Write a program which inputs a word (string) and outputs a perfect shuffle of that word.
1.2 Write a program to compute the number of repeated perfect shuffles required to reproduce the original input word.
1.3 Explore perfect shuffles of words which produce anagrams. For example, the second perfect shuffle of ‘PLATES’ is ‘PETALS’.
Solutions to these and related problems are developed here using J.
1.1 Perfect Shuffle¶
To begin with, a perfect shuffle can be done directly in J using the primitive verb /: (called Sort) for the given example:
This sorts the list on the left according to the order specified on the right (first is item from the left in position corresponding to 0 on the right, then item corresponding to 1, then 2, etc.).
The indices 0 2 4 6 8 1 3 5 7 9 here represent the order to select items for this particular perfect shuffle.
A J program to do a perfect shuffle for any input list is:
This program is named psh (for perfect shuffle). It is defined as a composition of verbs (functions) with implicit inputs — that is, without pronouns (variables) — and will be executed for an input y as y /: (shuffle y). See [1] for introduction to this "hook" structure. Here, the Sort verb /: uses the input list and the result of subprogram shuffle applied to the input list (which produces permutation indices such as shown above). Subprogram shuffle is defined as follows:
Here the primitive verb Grade-Up /: (using one input) is applied Atop (@) the result of subprogram perfect, which is:
These verbs are composed as a "fork" within a fork (see [1] for introduction), which will be executed for an input y as (#y) $ ((0:y),(1:y)).
Review of the J primitive verbs:¶
0:- (Zero) is a constant verb which returns
0. 1:- (One) is a constant verb which returns
1. ,- (Append) joins items on left to items on right. Example:
0,1is0 1. #- (Tally) counts the number of items in a list. Example:
# 'technology'is10. $- (Shape) extends a list of items on right to the length on left. Example:
10 $ 0 1is0 1 0 1 0 1 0 1 0 1. /:- (Grade-Up, with one input, as in subprogram
shuffle) returns indices to sort a list in ascending order. Example:/: 0 1 0 1 0 1 0 1 0 1is0 2 4 6 8 1 3 5 7 9. /:- (Sort, with two inputs, as in
psh) rearranges a list on the left into order specified on the right. Example:'technology' /: 0 2 4 6 8 1 3 5 7 9is'toelcohgny'.
To see intermediate results, execute the subprograms separately with the example input list:
To do a perfect shuffle, execute the main program:
Note that this program works for a list of any length — even or odd:
It works correctly for degenerate cases:
psh 'te' NB. Two characters
te
psh 't' NB. One character
t
psh '' NB. Empty list input
NB. Empty list result
It works for numbers as well as characters:
It works for an array of items:
And it works for boxed items:
psh 'A♠';'A♥';'A♦';'A♣';'K♠';'K♥';'K♦';'K♣'
┌──┬──┬──┬──┬──┬──┬──┬──┐
│A♠│K♠│A♥│K♥│A♦│K♦│A♣│K♣│
└──┴──┴──┴──┴──┴──┴──┴──┘ NB. 8 boxed 2-items
See [1] for introduction to arrays such as the matrix and boxed list above, as well as for definitions of primitive verbs , (Append) and ,: (Laminate) and ; (Link).
1.2 Period of Perfect Shuffles¶
J provides a primitive operator ^: (called Power) for iterating a verb (or program) on its own result — which is exactly what can be done here with psh to determine its period. Specifically, psh^:N 'technology' will iterate psh N times, starting with the input 'technology'. Doing several iterations at once traces the shuffles:
It is easy to repeat program psh enough times and find its period by inspection. It would be preferable, however, to have the computer iterate until the shuffled list matches the original list and just count the iterations. So, here is an iterative program to do that:
period =: 3 : 0
List =. Input =. ,y.
N =. 1
notmatch =. -.@-:
while. Input notmatch List =. psh List
do. N =. >:N
end. N
)
Explanation: This program is named period and is defined to be entered explicitly line-by-line. The first line assigns local pronouns named List and Input to be the original input (y.) ravelled (,) as a list. The next line assigns pronoun N to be 1. The next line defines a utility verb called notmatch to be Not (-.) Atop (@) Match (-:). The next three lines use a "while-do" control structure: while the original Input does not match the current List (which is repeatedly re-assigned to be the result of program psh), do Increment (>:) N. After this ends, the final result is N — the number of iterations. For example:
Better yet, mathematical analysis ([2],[3]) reveals that the period is the least common multiple of the lengths of the cycles of the permutation indices produced by /: applied to a shuffling pattern given as input. Hence, a more efficient definition is:
Explanation: Program Period is a composition of subprogram lcm Atop (@) subprogram cycles Atop (@) Grade-Up (/:). The input will be a list of numbers indicating the pattern for shuffling. For example, using the perfect pattern: /: 0 1 0 1 0 1 0 1 0 1 is 0 2 4 6 8 1 3 5 7 9. Then cycles 0 2 4 6 8 1 3 5 7 9 is 1 2 6 1. Subprogram cycles is a composition of verbs: C. (called Cycle-Direct) returns boxed lists of permutation cycles. For example, C. 0 2 4 6 8 1 3 5 7 9 is 0 and 6 3 and 8 7 5 1 2 4 and 9 in four boxes. Then > (Open) opens the boxes, and # (Tally) counts the items in each box — resulting in 1 2 6 1. Finally, subprogram lcm Inserts (/) the primitive function *. (Least Common Multiple) between each item, as in 1*.2*.6*.1, producing 6.
Note that an alternative program might well be defined directly on permutations (as pointed out by Roger Hui). Here, only the shuffle pattern is needed for input. For example:
Results of using either program for lists of different lengths to determine the period of perfect shuffles:
Length 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...
Period 1 1 2 2 4 4 3 3 6 6 10 10 12 12 4 4 8 8 18 18 ...
Such results may be produced automatically by the J program Periods =: Period@perfect\ with an input list of any length. See [1] for explanation of Prefix (\).
The reader may now study these results further.
1.3 Anagram Explorations¶
Anagrams can be explored using ^: (as shown earlier in section 1.2) with iterates up to the period. For example:
Words with correct spelling, such as 'maiden', can be found in a dictionary (manually or by computer).
Further explorations of related problems follow.
1.4 Inverse Perfect Shuffle¶
Here is a J program to undo a perfect shuffle:
This program is similar to psh but uses subprogram perfect instead of shuffle. Here the alternating 0s and 1s (produced by perfect) cause the inverse perfect shuffle directly. For example, 'technology' /: 0 1 0 1 0 1 0 1 0 1 sorts the list according to the positions of all the 0s then all the 1s. Thus:
Note that applying psh and its inverse ipsh (in either order) always reproduces the input:
1.5 Out-Shuffles and In-Shuffles¶
Actually, there are two different ways to perform a perfect shuffle. One is to start with the first item in the first half of the list (call this an "out-shuffle"). The other way is to start with the first item in the second half of the list (an "in-shuffle").
The programs developed so far perform an "out-shuffle". To perform an "in-shuffle" subprogram perfect could be modified easily to use 1:,0: instead of 0:,1:. Better yet, generalize (and simplify!) the main program to do both:
This program uses two inputs. The list is input on the left, and the input on the right specifies the shuffling pattern. Examples:
'technology' Psh 0 1 0 1 0 1 0 1 0 1 NB. Out-Shuffle
toelcohgny
'technology' Psh 1 0 1 0 1 0 1 0 1 0 NB. In-Shuffle
otleocghyn
Note the different uses of /: in a "hook" composition in program Psh. Sort (the first /: on the left) uses two inputs; whereas Grade-Up (the second /:) uses one input. Specifically, the in-shuffle example above is interpreted as 'technology' /: (/:1 0 1 0 1 0 1 0 1 0). See [1] for more explanation.
The period of an in-shuffle can be computed similarly. For example:
Resulting periods for different length in-shuffles are:
Length 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...
In-Period 1 2 2 4 4 3 3 6 6 10 10 12 12 4 4 8 8 18 18 6 ...
The reader may observe patterns in these periods and compare them with out-periods (from section 1.2):
Length 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...
Out-Period 1 1 2 2 4 4 3 3 6 6 10 10 12 12 4 4 8 8 18 18 ...
For instance, the out-period of length 2^n is n, and the in-period of length 2^n is 2n (for n>1). Also note that several in-periods are the same as their length. Questions: Are there any such out-periods (greater than 1)? Do any in-periods or out-periods exceed their length?
1.6 n Items and n Piles¶
The generalized Psh program can shuffle n items at a time. For example:
It also allows shuffles of more than two piles. For example:
Resulting periods for out-shuffles of (n) piles are:
Length 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Period (2) 1 1 2 2 4 4 3 3 6 6 10 10 12 12 4 4 8 8 18 18
Period (3) 1 3 4 4 6 2 2 6 5 5 11 6 6 15 16 16 52 4
Period (4) 1 4 6 3 3 7 9 5 5 18 10 2 2 8 84 9
Period (5) 1 5 6 10 6 6 9 12 11 6 6 15 44 42 9 9
More piles and more items-at-a-time can be handled similarly — as out-shuffles, in-shuffles, and various mid-shuffles. Indeed, program Psh can shuffle in any specified pattern.
Acknowledgements¶
Thanks to Lee Dickey, Murray Eisenberg, Roger Hui, Alan Lipp, Eugene McDonnell, Keith Smillie, and Norm Thomson for feedback on this article.
References¶
[0] Lipp, A. and Peelle, H. "Problem Solving by Programming: Perfect Shuffles", Journal of Computer Science Education, Vol. 9 No. 1, Fall 1994 p. 10
[1] Iverson, K. J Introduction and Dictionary, Iverson Software Inc., Toronto, 1995
[2] Thomson, N. "Roger and the Amazing Technicolor Ballclock", Vector, Vol. 12, No. 4, April 1996, p. 128