I rewrote two explicit and perhaps clearer versions of my sig verb. Both work
on the same principle as the original, but one uses a bit vector and the other
uses a list of indices, and the indices are a bit faster (pun probably
intended). I prefer the bit vector aesthetically though.
Both basically store the set of indices where possible lexicographically
minimal rotations could start (b and i in the verbs). On iteration n, the
starting index of rotations whose nth element is not minimal among the nth
elements of all possibly minimal rotations are removed from the aforementioned
set. The iteration continues until only one possible rotation is left, and for
a maximum of #y times, in which case all elements of y are identical and so any
rotation will do.
If I am not mistaken (I might be, have to hurry and go now), since there are a
maximum of #y iterations and each includes at most #y comparisons (= <./), the
number of comparisons is at worst quadratic in the length of y. This happens
when 1=#~.y, but most of the time this number is much smaller.
sigb=: (|.~ 3 : 0)"1
b=. 1"0 y
for. y do.
if. 1 = +/b do. break. end.
b=. (= <./)&.(b&#) y
y=. 1|.y
end.
b i. 1
)
sigi=: (|.~ 3 : 0)"1
i=. i.#y
for. y do.
if. 1 = #i do. break. end.
i=. i ((= <./)@:{ # [) y
y=. 1|.y
end.
i
)
Cheers,
Louis
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
