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
