J807-c, just now released, fixes the crash that my script detected. I
have a better version now anyway, given below.
Sample run:
canonize 1e6 $ 0 1
0 1 0 1 0 1...
Henry Rich
NB. Get # left-shifts to canonicalize y
canonnub =: ~:@:canonize =: ((|.~ canonshift =: 3 : 0)"1)
NB. Try each atom of y, in ascending order, until we find one that works
lowvalues =. 0$0 NB. In case no recursion possible, remember the first value
with the lowest frequency
for_t. /:~ ~. y do.
NB. Get the positions occupied by t. If they are more than half the
positions, skip t since it won't make much progress
if. (#y) < +: # tpos =. t I.@:= y do. continue. end.
NB. If there is only 1 position, it is the shift amount - return it
if. 1 = # tpos do. {. tpos return. end.
NB. get spacing between positions of t, including the wraparound
cyclt =. 2 -~/\ (, (#y) + {.) tpos
NB. If not all spacings are the same, recur on the positions of t to find a
canonical rotation
if. (}. -.@-: }:) cyclt do. (canonshift cyclt) { tpos return. end.
NB. All the distances between t values are the same. There is nothing to
choose between them. Try the next input value,
NB. but remember a shift value for the input that had the smallest frequency
if. (#tpos) < {.!._ lowvalues do. lowvalues =. (# , {.) tpos end.
end.
NB. No atom worked; must be aaaa... or abcabc...; canonize by moving smallest
to front
{: lowvalues NB. 0 if all values identical
)
On 2/21/2019 12:41 PM, 'Mike Day' via Programming wrote:
Have I missed an update, then?
Thanks,
Mike
Sent from my iPad
On 21 Feb 2019, at 16:58, Henry Rich <[email protected]> wrote:
The crash should be fixed in the latest released version, but I haven't
verified that.
Henry Rich
On Thu, Feb 21, 2019, 5:40 AM 'Mike Day' via Programming <
[email protected]> wrote:
Back to this thread...
I've worked up an explicit variant, sig3, using I. and E. - fairly
simple-minded,
but might be of interest. Also revisiting sig1 for comparison. sig3 is
not so good for
space, but is reasonably fast for the example.
NB. minmd =: (({.@:/:~)`(<./)@.(0-:{.@:(0&{.)))
minmd =: {.@:/:~ NB. this works for strings as well as numeric arrays
sig1 =: {.@(/:~)@:(|."0 1~) (I.@:= minmd)
NB. rotate each occurrence of minimum pair to front
sig2 =: 13 : '{./:~ y |."0 1~ i#~ (=minmd) y {~ <: i =. I. y = minmd y'
sig3 =: 3 : 0
b =. (,.~) y
NB. following replaces values by characters - assuming nub is small enough!
NB. but it doesn't appear to save space!
NB. b =. (,.~) ((~.@:,) (a.{~i.) ]) y
'm n' =. $y
bool =. m#1
for_pad. }.i.<: m do.
'a b' =. ({.;}.) b
if. bool{~<:pad do.
if. +/ i =. (n {.a) (+/@:E.)"1 b do.
bool =. 0 (pad + I.i) } bool
end.
end.
end.
bool
)
ts'~:sigb a'
0.000348269 6656
ts'~:sigi a'
0.000235419 6272
ts'~:sig3 a'
0.000233799 13248
ts'~:sig1"1 a'
0.000106371 7680
Also, I can confirm that Henry's canonical shift crashes this version of
Jqt
JVERSION
Engine: j807/j64/windows
Release-b: commercial/2019-01-22T18:51:16
Library: 8.07.22
Qt IDE: 1.7.9/5.9.6
Platform: Win 64
Installer: J807 install
InstallPath: c:/d/j807
Contact: www.jsoftware.com
Cheers,
Mike
On 16/02/2019 17:52, [email protected] wrote:
I rewrote two explicit and perhaps clearer versions of my sig verb. Both
work on the same principle as the original, but one uses a bit vector and
the other uses a list of indices, and the indices are a bit faster (pun
probably intended). I prefer the bit vector aesthetically though.
Both basically store the set of indices where possible lexicographically
minimal rotations could start (b and i in the verbs). On iteration n, the
starting index of rotations whose nth element is not minimal among the nth
elements of all possibly minimal rotations are removed from the
aforementioned set. The iteration continues until only one possible
rotation is left, and for a maximum of #y times, in which case all elements
of y are identical and so any rotation will do.
If I am not mistaken (I might be, have to hurry and go now), since there
are a maximum of #y iterations and each includes at most #y comparisons (=
<./), the number of comparisons is at worst quadratic in the length of y.
This happens when 1=#~.y, but most of the time this number is much smaller.
sigb=: (|.~ 3 : 0)"1
b=. 1"0 y
for. y do.
if. 1 = +/b do. break. end.
b=. (= <./)&.(b&#) y
y=. 1|.y
end.
b i. 1
)
sigi=: (|.~ 3 : 0)"1
i=. i.#y
for. y do.
if. 1 = #i do. break. end.
i=. i ((= <./)@:{ # [) y
y=. 1|.y
end.
i
)
Cheers,
Louis
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
----------------------------------------------------------------------
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
---
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
