In my tests, on longer sequences, Henry Rich's approach seemed about the same speed as mine.
Thanks, -- Raul On Sat, Dec 7, 2019 at 6:33 AM R.E. Boss <[email protected]> wrote: > Forcrand's solution is more or less the version I came up with, > unfortunately, it's far from linear (what is not compensated by its > elegance). > foo=: ,`(}.@])@.(0=(+{.))/ > ts'foo 1 _1 2 _2{~10000?.@#4' > 0.0166915 854720 > ts'foo 1 _1 2 _2{~100000?.@#4' > 1.9109807 6818496 > > Miller's solution is better in that respect (and much faster) > ts'an2 1 _1 2 _2{~10000?.@#4' > 0.0024111 722816 > ts'an2 1 _1 2 _2{~100000?.@#4' > 0.0281419 6293376 > > ddup from Rich also seems to be linear but is a factor 10 slower than an2 > ts'ddup 1 _1 2 _2{~10000?.@#4' > 0.0219618 395264 > ts'ddup 1 _1 2 _2{~100000?.@#4' > 0.2124874 3147776 > > Jasmin's solution is far too slow > ts'(delitemG~ 2, 0 i.~ 2&(+/\))(^:_) 1 _1 2 _2{~10000?.@#4' > 1.2363434 1585408 > > Thanks for all the contributions > > > R.E. Boss > > > > -----Oorspronkelijk bericht----- > > Van: Programming <[email protected]> > > Namens Louis de Forcrand > > Verzonden: zaterdag 7 december 2019 00:26 > > Aan: [email protected] > > Onderwerp: Re: [Jprogramming] Removing annihilating pairs > > > > Not particularly J-ish, but (array-shuffling aside) linear solution: > > > > s=: ,`(1}.])@.(= -@{.)/ > > s 1 _1 2 _2{~100?.@#4 > > 2 1 2 1 _2 _1 2 1 1 2 2 2 _1 2 _1 2 1 2 2 2 1 1 _2 _1 2 1 _2 _1 _2 _2 _2 > _2 _1 _2 _1 > > _1 _2 _2 1 1 1 2 1 _2 1 _2 _1 _1 _1 2 > > > > Since the reduced form of the input list is unique, we are free to > perform > > reductions in any order we please; in particular, we can start > simplifying from > > the back, which is what s does. > > Might do strange stuff on an empty input list. > > > > Cheers, > > Louis > > > > ----Original Message---- > > From : [email protected] > > Date : 06/12/2019 - 23:51 (CEST) > > To : [email protected] > > Subject : Re: [Jprogramming] Removing annihilating pairs > > > > If the answer to Jimmy's question is no, then the uniqueness of the > resulting > > array has to do (surprisingly) with free groups > > (https://en.wikipedia.org/wiki/Free_group). > > Indeed we can view a vector of numbers as a word over the alphabet [0,∞) > > of positive real numbers (where negative numbers / zero are inverses of > > letters in our alphabet). The fact that all maximal reductions > (reductions > > which contain no adjacent inverses) of a given word are equal means > exactly > > that our reduced list is unique. > > For a proof see: > > https://math.stackexchange.com/a/2425147 > > > > I'll look into this problem, it's interesting! > > Cheers, > > Louis > > > > ----Original Message---- > > From : [email protected] > > Date : 06/12/2019 - 23:36 (CEST) > > To : [email protected] > > Subject : Re: [Jprogramming] Removing annihilating pairs > > > > Hi, > > > > is the expected output of transforming 1 3 _3 3 5 to be 1 3 5 or 1 5 ? > > > > On Fri, Dec 6, 2019 at 7:15 AM R.E. Boss <[email protected]> wrote: > > > > > Given an array with zero or more annihilating pairs, i.e., two > > > subsequent numbers which add up to zero, the question is to clean up > > > the array by deleting all annihilating pairs such that no such pairs > are left. > > > I do have a solution that is both elegant and efficient (I believe), > > > but I am curious about other thoughts. > > > > > > foo 2 1 1 _1 2 _2 _1 > > > 2 > > > > > > foo 1 _1 2 _2{~100?.@#4 NB. Notice (?.) > > > 2 1 2 1 _2 _1 2 1 1 2 2 2 _1 2 _1 2 1 2 2 2 1 1 _2 _1 2 1 _2 _1 _2 _2 > > > _2 > > > _2 _1 _2 _1 _1 _2 _2 1 1 1 2 1 _2 1 _2 _1 _1 _1 2 > > > > > > > > > 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 > > > > ---------------------------------------------------------------------- > > 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
