Sometime in the early 1970s while I was working at STSC, Jeff Lewis, then a customer of ours at The Rouse Company, posed a challenging APL problem I named Progressive Dyadic Iota: devise an algorithm to find the index of each element of one vector in another where each successive element of the right argument should match the corresponding successive element of the left argument.
For example, if the left and right arguments were 'abacba' and 'baabaac', then the result would be
L←'abacba' ⋄ R←'baabaac'Notice how the first b in R matches the first b in L at index 2 and that the second b in R matches the second b in L at index 5, etc.
In other words, it was as if the elements of the left and right arguments had been labeled with subscripts indicating the successive positions of equal values:
'a_{1}b_{1}a_{2}c_{1}b_{2}a_{3}' ⍳ 'b_{1}a_{1}a_{2}b_{2}a_{3}a_{4}c_{1}'Labeling the successive equal elements of a vector as above is a job for the ranking function (i.e., ⍋⍋), as in
L,[0.5] ⍋⍋L⍳Lwhich labels the 'a's as 1 2 3, the 'b's as 4 5, and the lone 'c' as 6.
Applying this technique to both arguments and then looking up the right in the left solves the problem if the arguments satisfy several conditions:
With a little thought, it's easy to see that the third condition can be eliminated by using the left argument as the lookup vector on both sides:
L←'abacba' ⋄ R←'bcabaa'Next, we need a way to equalize the numbering on both sides. That is, the 'a's are already numbered the same on both sides, but the 'b's are not necessarily because there might be more 'a's in L than in R. This can be solved by including R in the lefthand double gradeup and similarly including L on the righthand side. In other words,
(⍋⍋L⍳L,R)⍳⍋⍋L⍳R,LNotice how this simple but important step of including the other argument on each side's lookup and ranking each lookup provides just the right balance. Not incidentally, the algorithm so far is now independent of the number of elements of each value in both arguments, thus eliminating the second condition.
Since we need only the first ⍴R elements of this expression for the result, we can reshape the righthand side of the middle iota, as in
(⍋⍋L⍳L,R)⍳(⍴R)⍴⍋⍋L⍳R,LWith the algorithm so far, if an element of R is not found in L, it'll be assigned a value of ⎕IO+(⍴L)+⍴R, but we actually need ⎕IO+⍴L. This can be solved by reshaping the lefthand side of the middle iota to the same shape as L, as in
L←'abacba' ⋄ R←'bcdabaa'thus eliminating the last remaining condition.
Thus, each argument to the middle iota is a ranking of the respective argument in L such that equal values in the two arguments have the same ranking on each side. It is this equal ranking which allows the middle iota to produce the correct result.
In other words, what we have done is similar to the labeling described above, but the indices are now sequential depending upon first the total number of 'a's, then the total number of 'b's, etc.
In the example below, there are seven 'a's between the two arguments, so the 'b's begin numbering with eight, even though the 'a's are numbered only from one to three in L and one to four in R. Continuing, there are four 'b's between the two arguments, so the 'c's begin numbering with twelve (the 'b's start at eight plus four of them).
Also, note that a_{4} in R is not found in L, so it is assigned an index of seven (i.e., ⎕IO+⍴L).
L←'abacba' ⋄ R←'baabaac'Note that the two sets of subscripts in statement (†) are exactly the left and right arguments to the middle iota. That is, the subscripts are unique such that we can dispense with the letters and just use the subscripts which is exactly what is done.
Here's the final function:
∇ Z←L pdi RAs Dyadic Iota and Epsilon are closely related, it should come as no surprise that there is a corresponding Progressive Dyadic Epsilon.
∇ Z←L pde RThat is, pdi and pde differ in their principal (and middle) function, only.
This latter function has some interesting uses such as in calculating an Asymmetric Difference between two multisets, where a multiset is a set (i.e. vector) with repeated elements. Asymmetric difference is like set difference, but where the multiplicity of each unique element in the left argument has subtracted from it the multiplicity of the same valued element in the right argument. If the difference between the multiplicities is positive, then that many copies of that element appear in the result. For multisets with no repeated elements, asymmetric difference and set difference produce the same results.
For example,
∇ Z←L mad RIf you have trouble displaying the APL characters on this page, likely it is due to either a browser setting (or an outofdate browser) or a missing font. Both Mozilla Firefox 2.0 or later and Internet Explorer 7 or later display the APL characters perfectly, but IE6 has some trouble. If this page doesn't display well with either APL Unicode font using any version of Internet Explorer, please try it again with Mozilla Firefox. Links for the two APL Unicode fonts as well as for Mozilla Firefox appear at the top of this page.
This page was created by Bob Smith — please any questions or comments about it to me. See my other APL projects.
NARS2000 © 20062020 

Comments or suggestions? Send them to . 