interval index

[Roger|Dyalog]

In previous posts, Membership and Index-Of, the game was to write functions f and g such that

      (x∊y) ≡ x f y
      (x⍳y) ≡ x g y

for non-empty integer vectors x and y, where f does not use ∊ and g does not use ⍳. Here, the game is to write a function h which does not use ⍸, so that for non-empty integer vectors x and y:

      x ←  {⍵[⍋⍵]} ¯100 + ? 5678 ⍴ 220
      y ←          ¯200 + ? 1234 ⍴ 440

      (x⍸y) ≡ x h y
1

⎕io←0 is assumed. ⎕io delenda est!

Outer Product

      ivo ← {¯1++/⍵∘.≥⍺}

      (x⍸y) ≡ x ivo y
1

This solution has the advantage of being rock solid, but the disadvantage of being O(n*2).

If the arguments were floating point numbers, ⎕ct←0 would be necessary because ⍸ is defined on exact comparisons.

Index Table

      ⍝
ivt←{
  r←(⌊/,⌈/)⍺
  i←(1+-/⌽r)⍴0
  i[⍺-⊃r]+←1
  i←¯1++\i
  (b×i[0⌈(⍵⌊⊃⌽r)-⊃r])-~b←⍵≥⊃r
}

      (x⍸y) ≡ x ivt y
1

This solution is blown out of the water if the range of values in ⍺ is large. Otherwise, it's pretty fast.

The 1+ in the expression i←(1+-/⌽r)⍴0 is an instance of the famous "off-by-1" pitfalls waiting to trap the unwary. One of my beefs with ⎕io is that it introduces opportunities for making an off-by-1 error where there was none.

Grade

      ivg ← {¯1+(≢⍺)↓i⊣i[i]←+\(≢⍺)>i←⍋⍺⍪⍵}

      (x⍸y) ≡ x ivg y
1

This solution is O(n) because ⍋ is O(n).

The algorithm first appeared as the function "classify" in §1.2 of Some Uses of { and }, 1987 and also in §14 of A History of APL in 50 Functions, 2016.

The unusual construct i⊣i[i]←blah can be made expressed in another way. Since i, being the result of ⍋, is (am?) a permutation, i⊣i[i]←⍳≢i is equivalent to ⍋i. That is, i[i]←blah assigns the items in the order ⍋i and is equivalent to blah[⍋i]. Therefore, ivg is equivalent to ivg1 (although ivg is a bit faster):

      ivg1 ← {¯1+(≢⍺)↓(+\i<≢⍺)[⍋i←⍋⍺⍪⍵]}

      (x⍸y) ≡ x ivg1 y
1