Essays/Progressive Index-Of
< Essays
Jump to navigation
Jump to search
Progressive index-of is like index-of except that each find "uses up" the target of that find. Thus:
oc=: i.~ (] - {) /:@/: NB. or [: ((] - {)~ /:) i.~ which is faster on non-integers pi=: #@[ ({. i.&(,.oc) }.) [ i. , x=: 'mississippi' y=: 'dismiss' x pi y 11 1 2 0 4 3 5 x i. y 11 1 2 0 1 2 2
The method is as follows:
0. Represent items of x and y by their indices in x .
] xi=. x i. x 0 1 2 2 1 2 2 1 8 8 1 ] yi=. x i. y 11 1 2 0 1 2 2
1. Stitch the occurrence counts to these indices, forming two 2-column integer matrices. The occurrence count of item i{x is the number of occurrences of that item that precedes i . That is, i{oc x is +/ (i{x) -:"_ _1 i{.x .
oc xi 0 0 0 1 1 2 3 2 0 1 3 oc yi 0 0 0 0 1 1 2 ] x2=. (,. oc) xi 0 0 1 0 2 0 2 1 1 1 2 2 2 3 1 2 8 0 8 1 1 3 ] y2=. (,. oc) yi 11 0 1 0 2 0 0 0 1 1 2 1 2 2
2. Do the ordinary i. on these 2-column matrices.
x2 i. y2 11 1 2 0 4 3 5 x pi y 11 1 2 0 4 3 5
Contributed by Roger Hui. An earlier version of the text previously appeared in the J Forum on 2002-02-18.