Reposted from the Partitions thread. <<<>>> Interesting. Erling's bitmap CombE help solves another category of Quora problems:
How many four digit numbers can be formed from the number 1,3,4,6,8 and 9 if repetition of digits is not allowed? <https://www.quora.com/How-many-four-digit-numbers-can-be-formed-from-the-number-1-3-4-6-8-and-9-if-repetition-of-digits-is-not-allowed> b =. 4 CombE 6 a =. 1 3 4 6 8 9 #c = b#a 15 NB. so the answer is 15. NB. What are the numbers? c 1 3 4 6 1 3 4 8 1 3 4 9 1 3 6 8 1 3 6 9 1 3 8 9 1 4 6 8 1 4 6 9 1 4 8 9 1 6 8 9 3 4 6 8 3 4 6 9 3 4 8 9 3 6 8 9 4 6 8 9 NB. Convert to decimal 10 10 10 10#. c 1346 1348 1349 1368 1369 1389 1468 1469 1489 1689 3468 3469 3489 3689 4689 I agree with Raul, This deserves a Wiki page. For that matter, the various combination verbs and partition verbs recently discussed in the programming forum also deserves a Wiki discussion page. Skip Cave Cave Consulting LLC On Mon, Nov 6, 2017 at 12:35 PM, Erling Hellenäs <[email protected]> wrote: > Hi all! > > New thread. > > Cheers, > > Erling Hellenäs > > > > -------- Forwarded Message -------- > Subject: Re: [Jprogramming] Partitions > Date: Mon, 6 Nov 2017 13:20:31 -0500 > From: Raul Miller <[email protected]> > Reply-To: [email protected] > To: Programming forum <[email protected]> > > > > 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 > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
