[Jprogramming] nubsieve modulo rotation
Raul Miller
rauldmiller at gmail.com
Thu Feb 14 17:13:22 UTC 2019
Probably "normalized".
Or, if I was really pressed for formal grammar and I had reason to
believe my audience was hostile to nouning verbs, "normal".
Thanks,
--
Raul
On Wed, Feb 13, 2019 at 10:26 PM Roger Hui <rogerhui.canada at gmail.com> wrote:
>
> And what would you use if you need a noun? Normal form? Again, more of a
> mouthful.
>
> Other terms I would use for identity problems, when explaining to laymen,
> is "ID number". They usually get it immediately.
>
>
> On Wed, Feb 13, 2019 at 6:55 PM Raul Miller <rauldmiller at gmail.com> wrote:
>
> > I like “normalize” personally.
> >
> > The ideas I associate with “signature” are not robust enough for a reliable
> > nub (and so would require additional care elsewhere).
> >
> > If that matters...
> >
> > Thanks,
> >
> > —
> > Raul
> >
> > On Wednesday, February 13, 2019, Roger Hui <rogerhui.canada at gmail.com>
> > wrote:
> >
> > > In this context, I prefer words like signature or representative rather
> > > than canonical form. Shorter and less scary and puts one's mind on the
> > > right track in multiple problems.
> > >
> > > e.g. What's a good representative for identity problems? ~. i. ] (index
> > > in nub). What's a good representative for ordering problems? (Seen a
> > > couple of weeks ago.) /:~@, i.!.0 ] (ordinals).
> > >
> > >
> > >
> > >
> > >
> > > On Wed, Feb 13, 2019 at 5:19 PM Henry Rich <henryhrich at gmail.com> wrote:
> > >
> > > > This is what I was looking for. It works on REB's testcase but has
> > less
> > > > than quadratic run time I think.
> > > >
> > > > NB. Get # left-shifts to canonicalize y
> > > >
> > > > canonshift =: 3 : 0
> > > >
> > > > NB. Try each atom of y until we find one that works
> > > >
> > > > for_t. /:~ ~. y do.
> > > >
> > > > NB. get spacing between positions of t, including the wraparound
> > > >
> > > > cyclt =. 2 -~/\ tpos =. (, (#y) + {.) t I.@:= y
> > > >
> > > > NB. if there is only 1 value, use its position
> > > >
> > > > if. 1 = # cyclt do. {. tpos end.
> > > >
> > > > NB. If all spacings are the same, try the next value
> > > >
> > > > if. (}. -: }:) cyclt do. continue. end.
> > > >
> > > > NB. Canonicalize cyclt. Use its result to canonicalize y
> > > >
> > > > (canonshift cyclt) { tpos return.
> > > >
> > > > end.
> > > >
> > > > NB. No atom worked; must be abcabc...; canonize by moving smallest to
> > > front
> > > >
> > > > (i. <./) y
> > > >
> > > > )
> > > >
> > > > ~: (|.~ canonshift)"1 a
> > > > 1 1 1 1 1 0 1 1 1 1 1 0
> > > >
> > > > The canonical form used here does not always put the smallest atom at
> > the
> > > > front, but I think it causes vector that differ only by a rotation to
> > > > canonicalize identically.
> > > >
> > > > Henry Rich
> > > >
> > > >
> > > >
> > > > On 2/13/2019 7:29 PM, Roger Hui wrote:
> > > > > Idea k: a minimum vector necessarily begins with a minimum
> > sub-sequence
> > > > in
> > > > > x,(k-1){.x of length k , itself necessarily begins with the minimal
> > > item.
> > > > >
> > > > >
> > > > > On Wed, Feb 13, 2019 at 9:52 AM Roger Hui <rogerhui.canada at gmail.com
> > >
> > > > wrote:
> > > > >
> > > > >> Yes, well, left as an exercise for the reader. :-)
> > > > >>
> > > > >> Idea: the minimum rotation of a vector necessarily begins with its
> > > > minimal
> > > > >> item.
> > > > >>
> > > > >> On Wed, Feb 13, 2019 at 9:34 AM Henry Rich <henryhrich at gmail.com>
> > > > wrote:
> > > > >>
> > > > >>> Yes; but now suppose the lines are very long. Is there a way to
> > find
> > > > >>> the signature (I would call it a canonical form) that doesn't
> > require
> > > > >>> enumerating rotations? (I haven't found a good way yet).
> > > > >>>
> > > > >>> Henry Rich
> > > > >>>
> > > > >>> On 2/13/2019 12:16 PM, Roger Hui wrote:
> > > > >>>> For each row, find a "signature", then find the nub sieve of the
> > > > >>>> signatures. The signature I use here is the minimum of all
> > possible
> > > > >>>> rotations.
> > > > >>>>
> > > > >>>> signature=: {. @ (/:~) @ (i.@# |."0 1 ])
> > > > >>>>
> > > > >>>> ~: signature"1 a
> > > > >>>> 1 1 1 1 1 0 1 1 1 1 1 0
> > > > >>>>
> > > > >>>>
> > > > >>>>
> > > > >>>>
> > > > >>>> On Wed, Feb 13, 2019 at 8:55 AM R.E. Boss <r.e.boss at outlook.com>
> > > > wrote:
> > > > >>>>
> > > > >>>>> Let the 12 x 20 matrix be defined by
> > > > >>>>> a=: 0 : 0
> > > > >>>>> 1 4 4 1 _4 _4 1 1 _4 _1 _1 _4 _4 _1 4 4 _1 _1 4 1
> > > > >>>>> 1 4 4 1 _4 _4 1 1 _4 _1 _1 _4 _4 _1 4 1 4 _1 _1 4
> > > > >>>>> 1 4 4 1 _4 _1 _4 1 1 _4 _1 _4 _4 _1 4 1 4 _1 _1 4
> > > > >>>>> 4 1 1 4 _1 4 1 _4 _4 1 _4 _1 _1 _4 1 _4 _1 4 4 _1
> > > > >>>>> 4 1 1 4 _1 4 1 _4 _4 1 1 _4 _1 _1 _4 _4 _1 4 4 _1
> > > > >>>>> _1 4 1 1 4 4 1 _4 _4 1 1 _4 _1 _1 _4 _4 _1 4 4 _1
> > > > >>>>> _1 4 4 _1 _4 _4 _1 _1 _4 1 1 _4 _4 1 4 4 1 1 4 _1
> > > > >>>>> _1 4 4 _1 _4 _4 _1 _1 _4 1 1 _4 _4 1 4 _1 4 1 1 4
> > > > >>>>> _1 4 4 _1 _4 1 _4 _1 _1 _4 1 _4 _4 1 4 _1 4 1 1 4
> > > > >>>>> 4 _1 _1 4 1 4 _1 _4 _4 _1 _4 1 1 _4 _1 _4 1 4 4 1
> > > > >>>>> 4 _1 _1 4 1 4 _1 _4 _4 _1 _1 _4 1 1 _4 _4 1 4 4 1
> > > > >>>>> 1 4 _1 _1 4 4 _1 _4 _4 _1 _1 _4 1 1 _4 _4 1 4 4 1
> > > > >>>>> )
> > > > >>>>>
> > > > >>>>> Required is the nubsieve for the items modulo rotation.
> > > > >>>>> So two arrays are considered to be equal if one is a rotation of
> > > the
> > > > >>> other.
> > > > >>>>> The answer I found is
> > > > >>>>> 1 1 1 1 1 0 1 1 1 1 1 0
> > > > >>>>>
> > > > >>>>>
> > > > >>>>> R.E. Boss
> > > > >>>>>
> > > > ----------------------------------------------------------------------
> > > > >>>>> For information about J forums see
> > > > http://www.jsoftware.com/forums.htm
> > > > >>>> ------------------------------------------------------------
> > > ----------
> > > > >>>> For information about J forums see
> > > > http://www.jsoftware.com/forums.htm
> > > > >>>
> > > > >>> ---
> > > > >>> This email has been checked for viruses by AVG.
> > > > >>> https://www.avg.com
> > > > >>>
> > > > >>> ------------------------------------------------------------
> > > ----------
> > > > >>> 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
More information about the Programming
mailing list