Probably it's just something going over my head, but how do these
permutations have more than one cycle?
#@C. _1 1 |."0 _ i. 128
1 1
C. y returns boxed cycles in permutation y.
What am I missing?
Jan-Pieter
On Fri, 17 Mar 2023, 01:07 Marshall Lochbaum, <mwlochb...@gmail.com> 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
