I can characterise the cycles of a permutation with (<.{~)^:_ (this keys each
cycle by its lowest element, but any unique key is fine).
But although this sometimes has log span (in the length of the longest cycle):
# (<.{~)^:(<_) _1|.i.128
8
The worst case is linear span:
# (<.{~)^:(<_) 1|.i.128
128
Is there anything with worst-case log span?
The best-case log span solution is basically an instance of pointer doubling.
But the reason is sometimes doesn't work is that we have no per-element key
which is monotonic in the order of elements within a cycle; <. is a crude
approximation. When there is an ascending run of permutation indices, <. can
drop down it in log time; but when the indices decrease, climbing takes linear
time as one element can get 'stuck' waiting for another. Is there any
workaround or alternative?
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
