Essays/Progressive Index-Of

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.