An AmuseBouche from APL History
Roger K.W. Hui
The phrase x[⍋⍒(⍴x)⍴0 1] appeared on the back of I.P. Sharp Tshirts
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, 19710611, page 21.

2: Mesh Problem (K.E. Iverson):
Given vectors a , b
and p such that a and b
are either both numeric or both character and
p∊ 0 1
(⍴a)=+/~p
(⍴b)=+/p
Write an APL expression whose value, in either origin, is the vector obtained
by storing consecutive values left to right of a into the 0’s
of p
and b into the 1’s of p .
For example:
a←'O JS'
b←'TMONE'
p←1 0 1 0 0 1 1 1 0
yields TOM JONES
There are two known minimal solutions.
(cf. Algorithm 48, APL ⍞, Vol. 11 No. 6).

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 386^{MAX} (and other) fame.
Mesh was described in §1.9
of A Programming Language, 1962:

A logical vector u
and the two vectors
a =
/c and
b = u/c,
obtained by compressing a vector c,
collectively determine the vector c.
The operation which specifies c
as a function of a, b, and
u is called a mesh
and is defined as follows:
If a and b are
arbitrary vectors and if u
is a logical vector such that +/
= ν(a) and +/u
= ν(b), then the mesh of
a and b on
u is denoted by
\a, u, b\
and is defined as the vector c
such that /c
= a and u/c
= b.
The mesh operation is equivalent to choosing successive
components of c from a
or b according as the successive components
of u are 0 or 1.
If, for example, a = (s, e, k),
b = (t, a), and
u = (0, 1, 0, 1, 0), then
\a, u, b\ =
(s, t, e, a, k). As a further example, …

Algorithm 48, entitled “Merging”, was a 13line branching
and looping function submitted by
James H. Burrill and Clark Wiedmann.
The 13 lines included one comment line and three errorchecking 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, 19711001, there were two relevant articles.
The first (page 52) was Algorithm 67 submitted
by H.J. Myers of the IBM San Jose Programming Center.

∇ z←a merge b
[1] ⍝Algorithm 48a
[2] →((⍴a←,a)>⍴b←,b)/e1
[3] z←b[⍋⍋a]
[4] →0
[5] e1:'length error'
∇

The second (page 61) was solution 2 in the problem section:

2. (a,b)[⍋⍋p] or (b,a)[⍋⍒p] .
This problem were incorrectly attributed to Ken Iverson
who has since informed me that he learned of it from Luthor Woodrum.
It illustrates a beautiful and succinct use of the sort operators.
Note the interesting relationship between the two solutions.
Using this idea, Algorithm 48 in Vol. 11, No. 6 of this magazine
can be shortened to
∇ z←a merge b
[1] →(0⍴a=b),0⍴∧/a
[2] z←b[⍋⍒a]
∇

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 (200505) and a
Dfunction page by John Scholes (20070305),
and is item 6 of
Sixteen APL AmuseBouches
by myself (20141027).
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 .
created:  20141025 09:10 
updated:  20141028 09:45 
