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
