Very nice. This deserves its own thread though. And possibly a wiki entry.
Thanks, -- Raul On Mon, Nov 6, 2017 at 10:31 AM, Erling Hellenäs <[email protected]> wrote: > Hi all! > > I made a version of comb, which uses bitmaps. > > 2 CombE 3 > 1 1 0 > 1 0 1 > 0 1 1 > (2 CombE 3) #"1 i.3 > 0 1 > 0 2 > 1 2 > > ts'12 comb 24' > 0.606316 9.02647e8 > ts'12 CombE 24' > 0.202434 2.82336e8 > ts'35 comb 40' > 1.39813 1.22167e9 > ts'35 CombE 40' > 0.268998 1.53241e8 > > CombE=: 4 : 0 > k=. <"1 (-i.1+d=.y-x)|."0 1 y{.1 > z=. (d$<(0,y)$0),<,:y#0 > for. i.x do. z=. k (+."1)&.> ,&.>/\. (_1&|."1)&.> z end. > ; z > ) > > Cheers, > > Erling Hellenäs > > > > > > > > > Den 2017-11-03 kl. 08:18, skrev Linda Alvord: >> >> You can compare the tree versions of comb3a and comb4 to see their >> differences: >> >> comb3a >> ┌─ [ >> │ ┌─ = >> │ ┌──────┤ ┌─ / ─── + >> │ │ └─ " ──┴─ 1 >> │ │ >> ├───┤ ┌─ |. >> ──┤ │ ┌─ @: ─┴─ I. >> │ ├─ @ ──┴─ # >> │ └─ ] >> │ >> │ ┌─ 2 >> │ │ ┌─ #: >> └───┤ ┌─ @ ──┴─ i. >> ├─ @: ─┴─ ^ >> └─ ] >> comb4 >> ┌─ [: >> ├─ |. >> │ ┌─ [: >> │ ├─ I. >> ──┤ │ ┌─ [ >> │ │ ├─ = >> │ │ │ ┌─ [: >> │ │ ┌───┤ │ ┌─ / ─── + >> └────┤ │ │ ├─ " ─┴─ 1 >> │ │ └────┤ >> │ │ │ ┌─ [: >> │ │ │ ├─ #: >> │ │ └─────┤ ┌─ [: >> │ │ │ ├─ i. >> └────┤ └─────┤ ┌─ 2 >> │ └────┼─ ^ >> │ └─ ] >> ├─ # >> │ ┌─ [: >> │ ├─ #: >> └───┤ ┌─ [: >> │ ├─ i. >> └────┤ ┌─ 2 >> └─────┼─ ^ >> └─ ] >> >> Linda >> >> -----Original Message----- >> From: Programming [mailto:[email protected]] On >> Behalf Of Linda Alvord >> Sent: Friday, November 3, 2017 2:28 AM >> To: [email protected] >> Subject: Re: [Jprogramming] Partitions >> >> Oops, this should be better: >> >> >> comb4=: 13 :'|.I.(x=+/"1#:i.2^y)##:i. 2^y' >> comb4 >> [: |. [: I. ([ = [: +/"1 [: #: [: i. 2 ^ ]) # [: #: [: i. 2 ^ ] >> #3 comb4 5 >> 10 >> Linda >> >> >> -----Original Message----- >> From: Programming [mailto:[email protected]] On >> Behalf Of Raul Miller >> Sent: Thursday, November 2, 2017 2:54 AM >> To: Programming forum <[email protected]> >> Subject: Re: [Jprogramming] Partitions >> >> No, you did not test your work. >> >> #3 comb 5 >> 10 >> #3 comb4 5 >> 56 >> >> Probably the simplest way to approach what I think you are trying to do >> involves expanding the part in parenthesis independent of the rest of it. >> >> And, personally, when I am working on a line of J code, I like to have a >> little test rig so that I can quickly see when I have gone astray. >> Doing that here (and clipping out my mistakes), then adding comments gets >> me this: >> >> First, I set up a test rig with the original expression: >> >> #3 ([ ((= +/"1) |.@:I.@# ]) 2 #:@i.@:^ ]) 5 >> 10 >> >> Then, I rephrase the outer part as an explicit expression for 13 : >> >> #3 (13 :'x ((= +/"1) |.@:I.@# ]) #:i. 2^y') 5 >> 10 >> >> Since that worked, I take a look at what 13 : gave me >> >> 13 :'x ((= +/"1) |.@:I.@# ]) #:i. 2^y' >> [ ((= +/"1) |.@:I.@# ]) [: #: [: i. 2 ^ ] >> >> Next, I try that out in my test rig: >> >> #3 ([ ((= +/"1) |.@:I.@# ]) [: #: [: i. 2 ^ ]) 5 >> 10 >> >> So, now that I have that, I do a rephrase of the inner part for another 13 >> : >> >> # 3([ (13 :'|.I.(x = +/"1 y) # y') [: #: [: i. 2 ^ ]) 5 >> 10 >> >> And, since that works, I take a look at what it gave me: >> >> [ (13 :'|.I.(x = +/"1 y) # y') [: #: [: i. 2 ^ ] [ ([: |. [: I. ] #~ [ >> = [: +/"1 ]) [: #: [: i. 2 ^ ] >> >> And, voila, I've got another variation that I can use in a word >> definition: >> >> comb4a=: [ ([: |. [: I. ] #~ [ = [: +/"1 ]) [: #: [: i. 2 ^ ] >> >> That's a bit ugly, but ascii is ugly (but, also, standardized and - thus - >> widely available). >> >> So, we can try that out and see it in operation: >> >> 3 comb4a 5 >> 0 1 2 >> 0 1 3 >> 0 1 4 >> 0 2 3 >> 0 2 4 >> 0 3 4 >> 1 2 3 >> 1 2 4 >> 1 3 4 >> 2 3 4 >> >> Also... note that when working with "real life" mechanisms (not just J), >> having some sort of test rig to make sure that what you are doing behaves >> like you think it does can be an invaluable time saver. (The alternative - >> putting a lot of work into something, only to find out that it doesn't work >> and that you have to start over again - is sometimes necessary but not >> always attractive.) >> >> (Well, that, and remember that this approach is slower than the stock comb >> implementation when y > 10 - so mostly I would just do require'stats' and >> then use that comb implementation.) >> >> Then again, now that we have this variation, we could also try to >> reconstruct an explicit expression which does the same thing. For that we >> want to merge these two examples: >> >> #3 (13 :'x ((= +/"1) |.@:I.@# ]) #:i. 2^y') 5 >> # 3([ (13 :'|.I.(x = +/"1 y) # y') [: #: [: i. 2 ^ ]) 5 >> >> Perhaps something like: >> #3 (13 :'|.I.(x = +/"1 t) # t=. #:i. 2^y') 5 >> 10 >> >> (But I would not blindly enshrine results just because they were generated >> by an automated mechanism - such things can be useful tools, of course, but >> if you abandon your own understanding that's not good.) >> >> I hope this helps, >> >> -- >> Raul >> >> On Wed, Nov 1, 2017 at 11:55 PM, Linda Alvord <[email protected]> >> wrote: >>> >>> This is another way to get to Raul's ideas in a tacit soluion: >>> >>> comb4=: 13 :'|.I.(x=+/"1#:i.x^y)##:i.x^y' >>> 2 comb4 4 >>> 0 1 >>> 0 2 >>> 0 3 >>> 1 2 >>> 1 3 >>> 2 3 >>> comb4 >>> [: |. [: I. ([ = [: +/"1 [: #: [: i. ^) # [: #: [: i. ^ >>> >>> Linda >>> >>> >>> -----Original Message----- >>> From: Programming [mailto:[email protected]] On >>> Behalf Of Lippu Esa >>> Sent: Wednesday, November 1, 2017 5:53 PM >>> To: '[email protected]' <[email protected]> >>> Subject: Re: [Jprogramming] Partitions >>> >>> Thank you, Raul! I knew that there would be a tacit solution. But comb is >>> better with big y as you said. >>> >>> Esa >>> >>> -----Original Message----- >>> From: Programming [mailto:[email protected]] On >>> Behalf Of Raul Miller >>> Sent: Wednesday, November 1, 2017 11:26 PM >>> To: Programming forum <[email protected]> >>> Subject: Re: [Jprogramming] Partitions >>> >>> comb3 performs well for y<10, but bogs down (compared to comb) for >>> y>10 >>> >>> That said, a=.[: #: [: i. 2 ^ ] is a verb, not a noun. >>> >>> That said, you do not have to compute a twice, for example: >>> >>> comb3a=: [ ((= +/"1) |.@:I.@# ]) 2 #:@i.@:^ ] >>> >>> (but comb3a is still slower than comb, when I time it, for y>10) >>> >>> Thanks, >>> >>> -- >>> Raul >>> >>> >>> On Wed, Nov 1, 2017 at 4:52 PM, Lippu Esa <[email protected]> wrote: >>>> >>>> Yes, interesting! Thank you Linda. >>>> >>>> Just for practice, I tried to isolate the common part: [: #: [: i. 2 ^ ] >>>> but had to use a noun as didn't manage to find a tacit solution. >>>> >>>> comb3=:([ = [: +/"1 a) ([: |. [: I. #) a=.[: #: [: i. 2 ^ ] >>>> >>>> Anyone? >>>> >>>> Esa >>>> >>>> -----Original Message----- >>>> From: Programming [mailto:[email protected]] >>>> On Behalf Of Linda Alvord >>>> Sent: Wednesday, November 1, 2017 1:49 PM >>>> To: [email protected] >>>> Subject: Re: [Jprogramming] Partitions >>>> >>>> Maybe you will find comb2 interesfing. >>>> >>>> load 'stats' >>>> >>>> comb2=:([ = [: +/"1 [: #: [: i. 2 ^ ]) ([: |. [: I. #) [: #: [: i. 2 >>>> ^ ] >>>> >>>> (4 comb2 7)-:4 comb 7 >>>> >>>> >>>> Li nda >>>> >>>> >>>> >>>> Get Outlook for Android<https://aka.ms/ghei36> >>>> >>>> ________________________________ >>>> From: Programming <[email protected]> on >>>> behalf of Erling Hellenäs <[email protected]> >>>> Sent: Wednesday, November 1, 2017 7:13:33 AM >>>> To: [email protected] >>>> Subject: Re: [Jprogramming] Partitions >>>> >>>> Hi all! >>>> >>>> parRuskey comparison. >>>> >>>> Mike Days new version is slightly faster than the Frank Ruskey version. >>>> >>>> Cheers, >>>> >>>> Erling Hellenäs >>>> >>>> ----------Project---------- >>>> >>>> ts=: 6!:2 , 7!:2@] NB. Time and space >>>> >>>> normalize=: 3 :0 >>>> NB. The idea here is to normalize the representation so that NB. the >>>> copies are adjacent. >>>> NB. Sort buckets within each combination after first item in each >>>> bucket v31=.(] /: {.&.>)"1 y NB. Sort buckets within each combination >>>> after number of items in each bucket v4=.(] /: #&.>)"1 v31 NB. Sort >>>> v5=. /:~ v4 >>>> (/: #&.> v5){ v5 >>>> ) >>>> >>>> compare=: -:&:normalize >>>> >>>> NB. parELMDE for comparison >>>> >>>> parELMDE=: 4 : 0 >>>> a =. ~. i.~"1 iy #: i. */ iy =. (1+i.x),(y-x)$x a =. a#~ x = #@~."1 a >>>> sort a </."1 i. y >>>> ) >>>> >>>> NB. Original Frank Ruskey version. >>>> >>>> parRuskey =: 4 : 0 >>>> a=: i. y >>>> r=: (0,y)$0 >>>> (x-1) S y-1 >>>> r </."1 i.y >>>> ) >>>> >>>> >>>> S =: 4 : 0 >>>> if. x=y do. >>>> r=:r,a >>>> else. >>>> for_i. i.x+1 do. >>>> a=: i y } a >>>> x S y-1 >>>> a=: y y } a >>>> end. >>>> if. x > 0 do. >>>> a=: x y } a >>>> (x-1) S y-1 >>>> a=: y y } a >>>> end. >>>> end. >>>> ) >>>> >>>> NB. Slightly modified by Erling to remove global variables. >>>> >>>> parRuskeyE =: 4 : 0 >>>> r=. (i.y) SE (x-1);y-1 >>>> r </."1 i.y >>>> ) >>>> >>>> SE =: 4 : 0 >>>> 'k n' =. y >>>> r=. 0{.,:x >>>> if. k=n do. >>>> r=.,:x >>>> else. >>>> for_i. i.k+1 do. >>>> r=.r, (i n } x) SE k;n-1 >>>> end. >>>> if. k > 0 do. >>>> r=.r, (k n } x) SE (k-1);n-1 >>>> end. >>>> end. >>>> r >>>> ) >>>> >>>> NB. Modified by Mike Day >>>> >>>> parRuskeyMD =: 4 : 0 >>>> NB. L =: 0$~0, 2 + y NB. debug/understand array of call parameters >>>> r=. (i.y) SMD (x-1),y-1 >>>> NB. R =: r NB. debug/understand output >>>> r </."1 i.y >>>> ) >>>> >>>> SMD =: 4 : 0 >>>> NB. L =: L, y, x NB. debug/understand array of call parameters >>>> 'k n' =. y >>>> a =.x >>>> r =. 0$~ 0, #a >>>> if. k = n - 1 do. NB. replace repeated calls with k = n (on entry) >>>> r =. (i.k+1) n }"0 1 (k+1)# ,:a NB. don't need to use recursion >>>> here! >>>> else. >>>> NB. is there a way to avoid recursion here, too? >>>> r =. r, ,/ (SMD&(k,n-1))"1 (i.k+1) n }"0 1 a NB.apply "1 instead >>>> of do loop end. >>>> if. k > 0 do. >>>> r=.r, (k n } a) SMD (k-1),n-1 >>>> end. >>>> r >>>> ) >>>> >>>> x=:1 >>>> y=:1 >>>> (x parELMDE y) compare x parRuskey y >>>> (x parELMDE y) compare x parRuskeyE y NB.(x parELMDE y) compare x >>>> parRuskeyMD y - Error >>>> x=:1 >>>> y=:2 >>>> (x parELMDE y) compare x parRuskey y >>>> (x parELMDE y) compare x parRuskeyE y (x parELMDE y) compare x >>>> parRuskeyMD y >>>> x=:2 >>>> y=:3 >>>> (x parELMDE y) compare x parRuskey y >>>> (x parELMDE y) compare x parRuskeyE y (x parELMDE y) compare x >>>> parRuskeyMD y >>>> x=:3 >>>> y=:5 >>>> (x parELMDE y) compare x parRuskey y >>>> (x parELMDE y) compare x parRuskeyE y (x parELMDE y) compare x >>>> parRuskeyMD y >>>> x=:3 >>>> y=:6 >>>> (x parELMDE y) compare x parRuskey y >>>> (x parELMDE y) compare x parRuskeyE y (x parELMDE y) compare x >>>> parRuskeyMD y >>>> >>>> x=:5 >>>> y=:10 >>>> ts'x parRuskey y' >>>> ts'x parRuskeyE y' >>>> ts'x parRuskeyMD y' >>>> >>>> >>>> -------Output------------------- >>>> >>>> >>>> x=:1 >>>> y=:1 >>>> (x parELMDE y) compare x parRuskey y >>>> 1 >>>> (x parELMDE y) compare x parRuskeyE y >>>> 1 >>>> NB.(x parELMDE y) compare x parRuskeyMD y - Error >>>> x=:1 >>>> y=:2 >>>> (x parELMDE y) compare x parRuskey y >>>> 1 >>>> (x parELMDE y) compare x parRuskeyE y >>>> 1 >>>> (x parELMDE y) compare x parRuskeyMD y >>>> 1 >>>> x=:2 >>>> y=:3 >>>> (x parELMDE y) compare x parRuskey y >>>> 1 >>>> (x parELMDE y) compare x parRuskeyE y >>>> 1 >>>> (x parELMDE y) compare x parRuskeyMD y >>>> 1 >>>> x=:3 >>>> y=:5 >>>> (x parELMDE y) compare x parRuskey y >>>> 1 >>>> (x parELMDE y) compare x parRuskeyE y >>>> 1 >>>> (x parELMDE y) compare x parRuskeyMD y >>>> 1 >>>> x=:3 >>>> y=:6 >>>> (x parELMDE y) compare x parRuskey y >>>> 1 >>>> (x parELMDE y) compare x parRuskeyE y >>>> 1 >>>> (x parELMDE y) compare x parRuskeyMD y >>>> 1 >>>> >>>> x=:5 >>>> y=:10 >>>> ts'x parRuskey y' >>>> 0.204245 3.89459e7 >>>> ts'x parRuskeyE y' >>>> 0.316044 3.8954e7 >>>> ts'x parRuskeyMD y' >>>> 0.173341 3.8954e7 >>>> >>>> >>>> Cheers, >>>> >>>> >>>> Erling Hellenäs >>>> >>>> >>>> Den 2017-10-31 kl. 20:17, skrev 'Mike Day' via Programming: >>>>> >>>>> parRuskeynew =: 4 : 0 >>>>> NB. L =: 0$~0, 2 + y NB. debug/understand array of call parameters >>>>> r=. (i.y) Snew (x-1),y-1 >>>>> NB. R =: r NB. debug/understand output >>>>> r </."1 i.y >>>>> ) >>>>> >>>>> Snew =: 4 : 0 >>>>> NB. L =: L, y, x NB. debug/understand array of call parameters >>>>> 'k n' =. y >>>>> a =.x >>>>> r =. 0$~ 0, #a >>>>> if. k = n - 1 do. NB. replace repeated calls with k = n (on entry) >>>>> r =. (i.k+1) n }"0 1 (k+1)# ,:a NB. don't need to use recursion >>>>> here! >>>>> else. >>>>> NB. is there a way to avoid recursion here, too? >>>>> r =. r, ,/ (Snew&(k,n-1))"1 (i.k+1) n }"0 1 a NB.apply "1 instead >>>>> of do loop end. >>>>> if. k > 0 do. >>>>> r=.r, (k n } a) Snew (k-1),n-1 >>>>> end. >>>>> r >>>>> ) >>>> >>>> --------------------------------------------------------------------- >>>> - 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 >> ---------------------------------------------------------------------- >> 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
