Roger's phrase 'lexicographically least rotation' was new to me, so i looked
it up in Wikipedia
<https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation>.
That article described several methods for finding the
"lexicographical minimum string rotation."
I will try to understand Roger's approach, and see if I can relate it to
the various approaches in the article.
Skip
On Sun, May 17, 2020 at 1:34 AM Roger Hui <rogerhui.can...@gmail.com> wrote:
> Since the lexicographically least rotation necessarily begins with the
> least element of a row,
>
> llr=: {. @ (/:~) @ (([: I. ] = <./) |."0 1 ])"1
>
> Less computation if the least element doesn't occur many times in a row.
>
> On Sat, May 16, 2020 at 10:59 PM Roger Hui <rogerhui.can...@gmail.com>
> wrote:
>
> > Find the lexicographically least of all the rotations of each row. Not
> > very efficient, but works.
> >
> > llr=: {.@(/:~)@(i.@# |."0 1 ])"1
> >
> > $ odo 3#5
> > 125 3
> > $ llr odo 3#5
> > 125 3
> > $ ~. llr odo 3#5
> > 45 3
> >
> >
> >
> > On Sat, May 16, 2020 at 10:50 PM Skip Cave <s...@caveconsulting.com>
> > wrote:
> >
> >> The acid test is to find all the rotational duplicates of a full
> odometer
> >> sequence:
> >>
> >> *odo=:#:i.@(*/)* NB. Odometer verb
> >>
> >> * $n=.odo 3#5 *
> >>
> >> *125 3*
> >>
> >> *rd=:3 :'(y i."_1 <./"1 y)|."_1 y'* NB. Roger's rotational duplication
> >> verb
> >>
> >> *$rdn=.rd n* NB. Return all rows to key form.
> >>
> >> *125 3*
> >>
> >> * $rdn1=.~. rdn* NB. Remove all duplicate keys.
> >>
> >> *55 3*
> >>
> >> * 5 11${rdn1*
> >>
> >> *┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐*
> >>
> >> *│0 0 0│0 0 1│0 0 2│0 0 3│0 0 4│0 1 0│0 1 1│0 1 2│0 1 3│0 1 4│0 2 0│*
> >>
> >> *├─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤*
> >>
> >> *│0 2 1│0 2 2│0 2 3│0 2 4│0 3 0│0 3 1│0 3 2│0 3 3│0 3 4│0 4 0│0 4 1│*
> >>
> >> *├─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤*
> >>
> >> *│0 4 2│0 4 3│0 4 4│1 1 1│1 1 2│1 1 3│1 1 4│1 2 1│1 2 2│1 2 3│1 2 4│*
> >>
> >> *├─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤*
> >>
> >> *│1 3 1│1 3 2│1 3 3│1 3 4│1 4 1│1 4 2│1 4 3│1 4 4│2 2 2│2 2 3│2 2 4│*
> >>
> >> *├─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤*
> >>
> >> *│2 3 2│2 3 3│2 3 4│2 4 2│2 4 3│2 4 4│3 3 3│3 3 4│3 4 3│3 4 4│4 4 4│*
> >>
> >> *└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘*
> >>
> >>
> >> We can see that some rotational dups were missed - 001-010, 002-020,
> etc.
> >> 112-121, 113-131, etc.
> >>
> >> So there is still some work to do on Roger's rb verb.
> >>
> >> Skip
> >>
> >>
> >>
> >> On Sat, May 16, 2020 at 8:21 PM Roger Hui <rogerhui.can...@gmail.com>
> >> wrote:
> >>
> >> > > I could be wrong.
> >> >
> >> > Right. I was wrong.
> >> >
> >> >
> >> > On Sat, May 16, 2020 at 6:18 PM Raul Miller <rauldmil...@gmail.com>
> >> wrote:
> >> >
> >> > > For example:
> >> > >
> >> > > A=: 2 3 1 2 1,: 2 1 2 3 1
> >> > > 2 1 |.("_1) A
> >> > > 1 2 1 2 3
> >> > > 1 2 3 1 2
> >> > > 2 4 |.("_1) A
> >> > > 1 2 1 2 3
> >> > > 1 2 1 2 3
> >> > >
> >> > > Thanks,
> >> > >
> >> > > --
> >> > > Raul
> >> > >
> >> > > On Sat, May 16, 2020 at 9:11 PM Roger Hui <
> rogerhui.can...@gmail.com>
> >> > > wrote:
> >> > > >
> >> > > > The question is, do you get a unique key (signature) if you
> rotate a
> >> > row
> >> > > so
> >> > > > that the first occurrence of the minimum value is first? I
> thought
> >> the
> >> > > > answer was yes after thinking about it for a minute. I could be
> >> wrong.
> >> > > >
> >> > > >
> >> > > > On Sat, May 16, 2020 at 5:53 PM Raul Miller <
> rauldmil...@gmail.com>
> >> > > wrote:
> >> > > >
> >> > > > > A critical question here is whether the minimum value can appear
> >> more
> >> > > > > than once in each row, or whether the examples (where each value
> >> is
> >> > > > > has a unique appearance in each row) are adequately complex.
> >> > > > >
> >> > > > > Thanks,
> >> > > > >
> >> > > > > --
> >> > > > > Raul
> >> > > > >
> >> > > > > On Sat, May 16, 2020 at 8:15 PM Roger Hui <
> >> rogerhui.can...@gmail.com
> >> > >
> >> > > > > wrote:
> >> > > > > >
> >> > > > > > Hmm, you just want the keys: rotate each row so that the
> minimum
> >> > > item is
> >> > > > > > first.
> >> > > > > >
> >> > > > > > (n i."_1 <./"1 n)|."_1 n
> >> > > > > > 1 3 2 4
> >> > > > > > 1 2 3 4
> >> > > > > > 1 2 3 4
> >> > > > > > 1 3 2 4
> >> > > > > > 1 3 2 4
> >> > > > > > 1 2 3 4
> >> > > > > > 1 2 3 4
> >> > > > > > 1 3 2 4
> >> > > > > >
> >> > > > > >
> >> > > > > > On Sat, May 16, 2020 at 5:11 PM Roger Hui <
> >> > rogerhui.can...@gmail.com
> >> > > >
> >> > > > > wrote:
> >> > > > > >
> >> > > > > > > ((n i."_1 <./"1 n)|."_1 n) </. n
> >> > > > > > > ┌───────┬───────┐
> >> > > > > > > │2 4 1 3│2 3 4 1│
> >> > > > > > > │3 2 4 1│3 4 1 2│
> >> > > > > > > │1 3 2 4│4 1 2 3│
> >> > > > > > > │4 1 3 2│1 2 3 4│
> >> > > > > > > └───────┴───────┘
> >> > > > > > >
> >> > > > > > > Rotate each row so that the minimum item is first, then use
> >> those
> >> > > > > rotated
> >> > > > > > > rows as keys.
> >> > > > > > >
> >> > > > > > >
> >> > > > > > > On Sat, May 16, 2020 at 4:44 PM Skip Cave <
> >> > s...@caveconsulting.com
> >> > > >
> >> > > > > wrote:
> >> > > > > > >
> >> > > > > > >> I have run across this issue a few times in the past.
> >> > > > > > >> The following 8x4 array has several rows that are
> 'rotational
> >> > > > > duplicates'.
> >> > > > > > >>
> >> > > > > > >> ]n=.8 4$2 4 1 3 2 3 4 1 3 4 1 2 3 2 4 1 1 3 2 4 4 1 2 3 1 2
> >> 3 4
> >> > 4
> >> > > 1 3
> >> > > > > 2
> >> > > > > > >>
> >> > > > > > >> 2 4 1 3
> >> > > > > > >>
> >> > > > > > >> 2 3 4 1
> >> > > > > > >>
> >> > > > > > >> 3 4 1 2
> >> > > > > > >>
> >> > > > > > >> 3 2 4 1
> >> > > > > > >>
> >> > > > > > >> 1 3 2 4
> >> > > > > > >>
> >> > > > > > >> 4 1 2 3
> >> > > > > > >>
> >> > > > > > >> 1 2 3 4
> >> > > > > > >>
> >> > > > > > >> 4 1 3 2
> >> > > > > > >>
> >> > > > > > >>
> >> > > > > > >> Is it possible to develop a verb that would find the rows
> >> that
> >> > are
> >> > > > > > >> rotational duplicates of each other. That is, find all the
> >> rows
> >> > > that
> >> > > > > would
> >> > > > > > >> be the same, if each row was rotated some integer value in
> >> the
> >> > > first
> >> > > > > > >> dimension. The output of the verb would be the same shape
> >> array,
> >> > > but
> >> > > > > with
> >> > > > > > >> each duplicate row rotated such that they show as
> identical.
> >> > > Picking
> >> > > > > the
> >> > > > > > >> 'standard' rotation for a set of rotational duplicates is
> up
> >> to
> >> > > the
> >> > > > > > >> implementer.
> >> > > > > > >>
> >> > > > > > >>
> >> > > > > > >> Skip
> >> > > > > > >>
> >> > >
> ----------------------------------------------------------------------
> >> > > > > > >> 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
> >> > > > >
> >> > > >
> >> ----------------------------------------------------------------------
> >> > > > 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
> >> >
> >> ----------------------------------------------------------------------
> >> 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
