Comparisons based on solutions offered.
(Beware of line-wrapping!)
v0=. ~:@:({.@(/:~)@(i.@# |."0 1 ]) "1) NB. RH
v1=. ~:@:(([: {.@/:~ {:@$ [\ (, }:))"1) NB. REB
v2=. ~:@:((|.~ >:@(# -~ {: i. 1:)@((_1 |. ] #^:_1 (= <./)@#~)^:(1 <
+/@])^:a: 1"0))"1)
NB. LdF
v3=. ~:@:((|.~ canonshift=. 3 : 0)"1) NB. HR
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
)
v4=. ~:@:(({.@(/:~)@:(|."0 1~) (I.@:=<./))"1) NB. MD (sig1)
v5=. ~:@:(([: {. [: /:~ ] |."0 1~ ([: I. ] = <./) #~ [: (= <./) ] {~ [: <:
[: I. ] = <./)"1)
NB. MD (sig2)
stp=. ] (([ ((<;._1 '|Sentence|Space|Time|Space * Time') , (, */&.:>@:(1
2&{))@:(] ; 7!:2@:] ; 6!:2)&>) (10{a.) -.&a:@:(<;._2@,~) ]) [ (0 0 $
13!:8^:((0 e. ])`(12"_)))@:(2 -:/\ ])@:(".&.>)@:((10{a.) -.&a:@:(<;._2@,~)
]) ::(0 0&$@(1!:2&2)@:('Mismatch!'"_))) ".@:('0( : 0)'"_)
A=: ". 12 59 $ (0 : 0) -. CRLF
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
)
JQt J807 (64 nonavx windows) performance results...
(v3 was excluded; otherwise, J crases (on v3 A)! Can anyone confirm?)
stp 111
v0 A
v1 A
v2 A
v4 A
v5 A
)
┌────────┬─────┬──────────┬────────────┐
│Sentence│Space│Time │Space * Time│
├────────┼─────┼──────────┼────────────┤
│ v0 A │15680│9.79728e_5│1.53621 │
├────────┼─────┼──────────┼────────────┤
│ v1 A │15680│4.4752e_5 │0.701711 │
├────────┼─────┼──────────┼────────────┤
│ v2 A │6016 │9.1532e_5 │0.550657 │
├────────┼─────┼──────────┼────────────┤
│ v4 A │7360 │4.14325e_5│0.304943 │
├────────┼─────┼──────────┼────────────┤
│ v5 A │6016 │5.29863e_5│0.318766 │
└────────┴─────┴──────────┴────────────┘
Corresponding J806 results...
(v3 is included.)
stp 111
v0 A
v1 A
v2 A
v3 A
v4 A
v5 A
)
┌────────┬─────┬──────────────┬────────────┐
│Sentence│Space│Time │Space * Time│
├────────┼─────┼──────────────┼────────────┤
│ v0 A │14336│0.000118566885│1.69977487 │
├────────┼─────┼──────────────┼────────────┤
│ v1 A │12160│5.34553436e_5 │0.650016979 │
├────────┼─────┼──────────────┼────────────┤
│ v2 A │11264│0.000124958141│1.4075285 │
├────────┼─────┼──────────────┼────────────┤
│ v3 A │18688│0.000427807898│7.99487399 │
├────────┼─────┼──────────────┼────────────┤
│ v4 A │7296 │4.23078038e_5 │0.308677736 │
├────────┼─────┼──────────────┼────────────┤
│ v5 A │6272 │5.04595455e_5 │0.31648227 │
└────────┴─────┴──────────────┴────────────┘
On Thu, Feb 14, 2019 at 11:27 AM 'Mike Day' via Programming <
[email protected]> wrote:
> FWIW, slightly better and faster versions of my rushed efforts of
> yesterday
>
> NB. rotate each occurrence of minimum to front
> sig1 =: {.@(/:~)@:(|."0 1~) (I.@:=<./)
>
> NB. rotate each occurrence of minimum with minimum left neighbour
> sig2 =: 13 : '{./:~ y |."0 1~ i#~ (=<./) y{~ <: i =. I. y = <./ y'
>
> Still not too elegant, but quite fast for the small example, a. Don’t
> know about bigger arrays.
>
> Mike
>
> Sent from my iPad
>
> > On 14 Feb 2019, at 03:26, Roger Hui <[email protected]> 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 <[email protected]>
> 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 <[email protected]>
> >> 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 <[email protected]>
> 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 <[email protected]
> >>>
> >>>> 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 <[email protected]>
> >>>> 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 <[email protected]>
> >>>> 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
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
