Oh, nice! I tried <./{~^:(<2>.@^.#p)p, but that loses information; your
solution retains it in m.
On Thu, 16 Mar 2023, Marshall Lochbaum wrote:
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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
