Partition the matrix by the smallest element, then work separately on each
partition.
On Tue, May 19, 2020 at 8:11 PM Skip Cave <s...@caveconsulting.com> wrote:
> Testing Roger's rotational duplicate finder:
>
> ts=:6!:2 , 7!:2@]
>
> $x=.odo 8#8
>
> 16777216 8
>
> ts 't0=.llr0 x'
>
> 37.0263 2.14749e9
>
> ts 't1=.llr1 x'
>
> 26.6041 2.14749e9
>
> ts 't3=.llr3 x'
>
> 34.1857 1.28849e10
>
> ts 't2=.llr2 x'
>
> |out of memory: llr2
>
> | (c*i.n){}."1/:~(c#i.n),.((n*c)$i.c) |."_1 c#y
>
> ts=:6!:2 , 7!:2@]
>
>
> It looks like fairly lengthy runtimes for 8 integers. For more than 8-10
> elements we may need a more efficient algorithm.
>
>
> Skip Cave
> Cave Consulting LLC
>
>
> On Tue, May 19, 2020 at 9:14 PM Roger Hui <rogerhui.can...@gmail.com>
> wrote:
>
> > I think in such cases you ought to do i.!.0~x first (as the write-up
> points
> > out). Then you'd be working with small-range integers and the maximum
> > element shouldn't cause a problem. Unless you are working with a huge x.
> > In which case you have other problems.
> >
> > On Tue, May 19, 2020 at 6:32 PM Raul Miller <rauldmil...@gmail.com>
> wrote:
> >
> > > Perhaps worth noting that the "radius limit" is calculable based on
> > > the type of the numbers in the argument.
> > >
> > > For integer values, on a 64 bit machine, radius*#y should not exceed
> > > 9223372036854775807
> > >
> > > datatype 9223372036854775807
> > > integer
> > > datatype 9223372036854775807+1
> > > floating
> > >
> > > It gets a little more complicated with floating point values, because
> > > there the minimum difference between elements in a row is essential
> > > for the calculation. If this is deemed to be worth to bother, it can
> > > be calculated using 0 -.~ 2 -/\ \:~ row and finding the minimum
> > > non-zero value. (If this is an empty list, all rows are already in
> > > their canonical configuration.) If this value is available,
> > > radius*mindiff*#y should not exceed 9007199254740991. (A convservative
> > > approximation would be to verify that there are no fractional values
> > > and use mindiff=.1)
> > >
> > > Not sure that this is worth the effort, but... anyways...
> > >
> > > FYI,
> > >
> > > --
> > > Raul
> > >
> > > On Tue, May 19, 2020 at 11:37 AM Roger Hui <rogerhui.can...@gmail.com>
> > > wrote:
> > > >
> > > > I have written a lengthier description
> > > > <https://forums.dyalog.com/viewtopic.php?f=30&t=1642> of the
> solutions
> > > in
> > > > the Dyalog APL Chat Forum. It is in APL rather than J notation, but
> > may
> > > be
> > > > helpful. The main thing to remember is that " (the rank operator)
> is ⍤
> > > in
> > > > Dyalog APL.
> > > >
> > > >
> > > >
> > > > On Sun, May 17, 2020 at 10:44 PM Skip Cave <s...@caveconsulting.com>
> > > wrote:
> > > >
> > > > > Roger,
> > > > > The llr versions you provided are interesting and useful. I expect
> to
> > > learn
> > > > > much by analysing them.
> > > > >
> > > > > Skip Cave
> > > > >
> > > > >
> > > > >
> > > > > On Sun, May 17, 2020 at 3:09 PM Roger Hui <
> rogerhui.can...@gmail.com
> > >
> > > > > wrote:
> > > > >
> > > > > > (I posted the following msg which appears not to be distributed.
> > > Not yet
> > > > > > in the archive, at least. Sorry if you receive this more than
> > once.)
> > > > > >
> > > > > > llr0=: {.@(/:~)@(i.@# |."0 1 ])"1
> > > > > >
> > > > > > llr1=: {.@(/:~)@(([: I. ] = <./)|."0 1 ])"1
> > > > > >
> > > > > > llr2=: 3 : 0
> > > > > > c=. {: $ y
> > > > > > n=. # y
> > > > > > (c*i.n) { }."1 /:~ (c#i.n) ,. ((n*c)$i.c) |."_1 c # y
> > > > > > )
> > > > > >
> > > > > > llr3=: 3 : 0
> > > > > > c=. {: $ y NB. # columns
> > > > > > n=. # y NB. # rows
> > > > > > r=. >:+:>./|,y NB. the "radius"
> > > > > > q=. y + r*i.n NB. increase each row by the radius
> > > > > > e=. <./"1 q NB. minimum in each row
> > > > > > b=. q=e NB. where elements equal the minimum
> > > > > > s=. +/"1 b NB. # times that happens for each row
> > > > > > (r*i.n) -~ (}:+/\0,s) { /:~ (c|I.,b) |."_1 s#q
> > > > > > )
> > > > > >
> > > > > > llr0 computes the lexicographically least rotation of all the
> > > rotations
> > > > > of
> > > > > > each row.
> > > > > >
> > > > > > llr1 computes the LLR of, each row rotated so that every minimal
> > > element
> > > > > > gets the chance to be the first element.
> > > > > >
> > > > > > llr2 is llr0 reworked so that the code works on the entire matrix
> > at
> > > > > once,
> > > > > > rather than one row at a time.
> > > > > >
> > > > > > llr3 likewise, llr2 reworked to work on the entire matrix at
> once.
> > > It
> > > > > > assumes that the maximal element in the entire matrix (needed for
> > the
> > > > > > "radius") is no so large as to consume all available precision.
> > > > > >
> > > > > > odo=: #: i.@(*/)
> > > > > > x=: ,.~ ,~ odo 5$5
> > > > > > $x
> > > > > > 6250 10
> > > > > >
> > > > > > (llr0 -: llr1) x
> > > > > > 1
> > > > > > (llr0 -: llr2) x
> > > > > > 1
> > > > > > (llr0 -: llr3) x
> > > > > > 1
> > > > > >
> > > > > > timer=: 6!:2
> > > > > > timer&> 'llr0 x'; 'llr1 x'; 'llr2 x'; 'llr3 x'
> > > > > > 0.0434449 0.0141476 0.0207071 0.00634583
> > > > > >
> > > > > >
> > > > > > On Sat, May 16, 2020 at 4:44 PM Skip Cave <
> s...@caveconsulting.com
> > >
> > > > > wrote:
> > > > > >
> > > > > > > I have run across this issue a few times in the past.
> > > > > > > The following 8x4 array has several rows that are 'rotational
> > > > > > duplicates'.
> > > > > > >
> > > > > > > ]n=.8 4$2 4 1 3 2 3 4 1 3 4 1 2 3 2 4 1 1 3 2 4 4 1 2 3 1 2 3
> 4 4
> > > 1 3 2
> > > > > > >
> > > > > > > 2 4 1 3
> > > > > > >
> > > > > > > 2 3 4 1
> > > > > > >
> > > > > > > 3 4 1 2
> > > > > > >
> > > > > > > 3 2 4 1
> > > > > > >
> > > > > > > 1 3 2 4
> > > > > > >
> > > > > > > 4 1 2 3
> > > > > > >
> > > > > > > 1 2 3 4
> > > > > > >
> > > > > > > 4 1 3 2
> > > > > > >
> > > > > > >
> > > > > > > Is it possible to develop a verb that would find the rows that
> > are
> > > > > > > rotational duplicates of each other. That is, find all the rows
> > > that
> > > > > > would
> > > > > > > be the same, if each row was rotated some integer value in the
> > > first
> > > > > > > dimension. The output of the verb would be the same shape
> array,
> > > but
> > > > > with
> > > > > > > each duplicate row rotated such that they show as identical.
> > > Picking
> > > > > the
> > > > > > > 'standard' rotation for a set of rotational duplicates is up to
> > the
> > > > > > > implementer.
> > > > > > >
> > > > > > >
> > > > > > > Skip
> > > > > > >
> > > ----------------------------------------------------------------------
> > > > > > > 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
