Interesting problem! I think this works: for starting permutation p,
keep two lists. At step i,
- l is {~^:i p, that is, the index 2^i steps further along the cycle
- m is the minimum index among those less than 2^i steps ahead.
Initially l is p and m is i.#p . To update, simultaneously replace l
with {~l and m with m<.l{m . This last expression is the minimum of
steps i.2^i and (2^i)+i.2^i , which covers i.2^i+1 in total.
One rendition of the whole thing:
1{:: ({~@[ ; ]<.{)&>/^:(>.2^.#p) (;i.@#) p
I haven't come up with a nice way to write the termination condition so
I just used a logarithmic number of steps, since as soon as 2^i exceeds
the length of the permutation all indices have been covered. It should
be safe to stop when m stops changing (in general, l won't), and that
would give time proportional to the log of the longest cycle.
Marshall
On Thu, Mar 16, 2023 at 03:20:25PM -0700, Elijah Stone wrote:
> 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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
