[Jprogramming] nubsieve modulo rotation

[Henry Rich]

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