An Amuse-Bouche from APL History The phrase x[⍋⍒(⍴x)⍴0 1] appeared on the back of I.P. Sharp T-shirts in the 1970s and 1980s. It performs a perfect shuffle. x←'ABCDEFGHIJKLMNOPQ' x[⍋⍒(⍴x)⍴0 1] IAJBKCLDMENFOGPHQ I was curious about its provenance and found the following: Smith, Robert A., Problem Section, APL Quote Quad,
Volume 3, Number 1,
Robert A. Smith of Laurel, Maryland was the editor of the problem section in the APL Quote Quad. He is now better known as Bob Smith of Boolean Bob, NARS, NARS2000, and 386MAX (and other) fame. Mesh was described in §1.9 of A Programming Language, 1962:
Algorithm 48, entitled “Merging”, was a 13-line branching and looping function submitted by James H. Burrill and Clark Wiedmann. The 13 lines included one comment line and three error-checking lines. There was an additional note that the function can be used to merge, rearrange, or rotate vectors. In the immediately following issue of the APL Quote Quad, Volume 3,
Number 2 & 3,
The second (page 61) was solution 2 in the problem section:
From the above, we can say that the mesh problem was due to Ken Iverson and the solution to Luthor Woodrum and perhaps to H.J. (Joseph) Myers. More recently, x[⍋⍒(⍴x)⍴0 1] is the subject of a
Vector article
by Norman Thomson (2005-05) and a
D-function page by John Scholes ( In Dyalog APL, mesh can be implemented as a monadic operator: M←{(⍺,⍵)[⍋⍋⍺⍺]} ⍝ or M←{(⍵,⍺)[⍋⍒⍺⍺]} 'O JS' (1 0 1 0 0 1 1 1 0 M) 'TMONE' TOM JONES The “selfie” x(b M)x or b M⍨ x (same left and right arguments) is equivalent to the merge functions described above. Moreover: 1 0 1 1 1 1 1 M⍨ ⍳7 1 0 2 3 4 5 6 1 1 1 1 1 1 0 M⍨ ⍳7 1 2 3 4 5 6 0 These two permutations, p←(⌽⍳2⌊n),2↓⍳n and q←1⌽⍳n , suffice to generate the entire group of permutations of order n (see §4.4 of my APL87 paper or exercise 2.10.11 of Herstein’s Topics in Algebra). Therefore, repeated application of M with left arguments 1≠⍳n and n≠1+⍳n suffice to effect any permutation of a vector of length n .
|