Hmm... Remember that
combboolT=: [: ; masks (or merge@:shift)^:(1 + -~/@$@:>@[) start And, the left verb for ^: produces a value of 2 for 2 combboolT 4 So, this gives the same result: M=: 2 masks 4 S=: 2 start 4 ; M (or merge@:shift) M (or merge@:shift) S I hope this helps (and I hope you can see why repeating the operation twice gives the same result as ^:2 on that operation). Anyways, I like to do some of the evaluation myself so I can use the computer to help focus on the other parts. Thanks, -- Raul On Sun, Nov 12, 2017 at 4:06 AM, Linda Alvord <[email protected]> wrote: > Now I'm ready to tackle this display: > > Load 'debug' > Dissect 'I. 2 combboolT 4' > > It may be a while until you hear from me. > > Linda > > > -----Original Message----- > From: Programming [mailto:[email protected]] On Behalf > Of Linda Alvord > Sent: Sunday, November 12, 2017 3:55 AM > To: [email protected] > Subject: Re: [Jprogramming] K-sets - bitmap representation of sets. WAS: > Partitions > > > Raul, Shouldn't your last line be: > > I. 2 combboolT 4 > > Linda > > > > -----Original Message----- > From: Programming [mailto:[email protected]] On Behalf > Of Raul Miller > Sent: Sunday, November 12, 2017 1:32 AM > To: Programming forum <[email protected]> > Subject: Re: [Jprogramming] K-sets - bitmap representation of sets. WAS: > Partitions > > I couldn't resist making a more concise tacit implementation of combbool: > > or=. +."1&.> > merge=. ,&.>/\. > shift=. _1&|."1&.> > masks=. -@,.@i.@(1--) <@|. {.&1@] > start=. (1 ,.@{.~ --1:) <@# ,:@#&0@] > > combboolT=: [: ; masks (or merge@:shift)^:(1 + -~/@$@:>@[) start > combboolT=: combboolT f. > > The only "hard" part was reconstituting the x argument to combbool (the > number of items in each combination) from the arguments being used for the > induction. That's the (1 + -~/@$@:>@[) part. > > Here, 'masks' is the constant argument used at each stage of induction, and > 'start' represents the 0 items being combined case, in a format compatible > with induction: > > 2 masks 4 > ┌───────┬───────┬───────┐ > │1 0 0 0│0 1 0 0│0 0 1 0│ > └───────┴───────┴───────┘ > 2 start 4 > ┌────┬────┬───────┐ > │ │ │0 0 0 0│ > └────┴────┴───────┘ > > And, I can extract the original left argument from the masks argument: > > (1 + -~/@$@:>) 3 masks 7 > 3 > (1 + -~/@$@:>) 4 masks 7 > 4 > (1 + -~/@$@:>) 0 masks 7 > 0 > > Note that this kind of thing, while slightly annoying, does not alter the > big-O structure of the implementation. > > Anyways... it works: > > I. 2 combbool 4 > 0 1 > 0 2 > 0 3 > 1 2 > 1 3 > 2 3 > > Thanks, > > -- > Raul > > On Fri, Nov 10, 2017 at 5:37 PM, Jose Mario Quintana > <[email protected]> wrote: >> Hi Erling, >> >> I could not resist the temptation of making tacit (fixed) versions of >> combbool and combbit, >> >> ". noun define -. CRLF >> >> CombBool=. >> >> ;@:(3&({::))@:((<@:(2&({::) ([ +."1&.> ,&.>/\.@:(_1&|."1&.>)@:]) 3 >> &({::)) 3} ])^:(0&({::)))@:(<@:(0&({::) ((-~ $ <@:(0 $~ 0 , ])) , >> <@:,:@:(0 #~ ])) 1&({::)) 3} ])@:(<@:(0&({::) <"1@:(-@:i.@:(1 + -~ >> ) (|."0 1) 1 {.~ ]) 1&({::)) 2} ])@:(,&(<;._1 ' K Z')@:;) >> >> ) >> >> >> ". noun define -. CRLF >> >> CombBit=. >> >> #:@:;@:(3&({::))@:((<@:(2&({::) ([ 23 b.&.> ,&.>/\.@:(_1&(33 b.)&. >>>)@:]) 3&({::)) 3} ])^:(0&({::)))@:(<@:(0&({::) ((<0) ,~ (<i.0) $~ >> -~) 1&({::)) 3} ])@:(<@:(0&({::) <"0@:((1) 33 b.~ ] - >:@:i.@:>:@ >> :(-~)) 1&({::)) 2} ])@:([ (0 0 $ 13!:8^:((0 e. ])`(12"_)))@:(63 >: >> 1&({::)))@:(,&(<;._1 ' K Z')@:;) >> >> ) >> >> and comparing them using my performance utility stp, >> >> ". noun define -. CRLF >> >> stp=. >> >> ] (([ ((<;._1 '|Sentence|Space|Time|Space * Time') , (, */&.:>@:(1 >> 2&{))@:(] ; 7!:2@:] ; 6!:2)&>) (10{a.) -.&a:@:(<;._2@,~) ]) [ (0 >> 0 $ 13!:8^:((0 e. ])`(12"_)))@:(2 -:/\ ])@:(".&.>)@:((10{a.) -.&a: >> @:(<;._2@,~) ]) ::(0 0&$@(1!:2&2)@:('Mismatch!'"_))) ".@:('0( : 0) >> '"_) >> >> ) >> >> running on, >> >> Engine: j806/j64avx/windows >> Beta-7: commercial/2017-10-26T16:19:05, >> >> These are some results (stp verifies that the products match), >> >> stp 111 >> 2 combbool 4 >> 2 CombBool 4 >> 2 combbit 4 >> 2 CombBit 4 >> ) >> ┌──────────────┬─────┬──────────┬────────────┐ >> │Sentence │Space│Time │Space * Time│ >> ├──────────────┼─────┼──────────┼────────────┤ >> │ 2 combbool 4│8960 │1.47721e_5│0.132358 │ >> ├──────────────┼─────┼──────────┼────────────┤ >> │ 2 CombBool 4│5120 │1.329e_5 │0.0680449 │ >> ├──────────────┼─────┼──────────┼────────────┤ >> │ 2 combbit 4│8704 │1.40379e_5│0.122186 │ >> ├──────────────┼─────┼──────────┼────────────┤ >> │ 2 CombBit 4│4864 │1.00131e_5│0.0487035 │ >> └──────────────┴─────┴──────────┴────────────┘ >> >> stp 111 >> 5 combbool 11 >> 5 CombBool 11 >> 5 combbit 11 >> 5 CombBit 11 >> ) >> ┌───────────────┬─────┬──────────┬────────────┐ >> │Sentence │Space│Time │Space * Time│ >> ├───────────────┼─────┼──────────┼────────────┤ >> │ 5 combbool 11│34304│3.94621e_5│1.35371 │ >> ├───────────────┼─────┼──────────┼────────────┤ >> │ 5 CombBool 11│25344│3.46976e_5│0.879377 │ >> ├───────────────┼─────┼──────────┼────────────┤ >> │ 5 combbit 11│28544│3.06076e_5│0.873662 │ >> ├───────────────┼─────┼──────────┼────────────┤ >> │ 5 CombBit 11│21760│2.39911e_5│0.522046 │ >> └───────────────┴─────┴──────────┴────────────┘ >> >> stp 11 >> 8 combbool 17 >> 8 CombBool 17 >> 8 combbit 17 >> 8 CombBit 17 >> ) >> ┌───────────────┬───────┬───────────┬────────────┐ >> │Sentence │Space │Time │Space * Time│ >> ├───────────────┼───────┼───────────┼────────────┤ >> │ 8 combbool 17│1577216│0.00107731 │1699.15 │ >> ├───────────────┼───────┼───────────┼────────────┤ >> │ 8 CombBool 17│1309568│0.00102874 │1347.21 │ >> ├───────────────┼───────┼───────────┼────────────┤ >> │ 8 combbit 17│1052160│0.000774327│814.716 │ >> ├───────────────┼───────┼───────────┼────────────┤ >> │ 8 CombBit 17│1051136│0.000731325│768.722 │ >> └───────────────┴───────┴───────────┴────────────┘ >> >> stp 1 >> 60 combbool 63 >> 60 CombBool 63 >> 60 combbit 63 >> 60 CombBit 63 >> ) >> ┌────────────────┬────────┬──────────┬────────────┐ >> │Sentence │Space │Time │Space * Time│ >> ├────────────────┼────────┼──────────┼────────────┤ >> │ 60 combbool 63│17328128│0.0452368 │783869 │ >> ├────────────────┼────────┼──────────┼────────────┤ >> │ 60 CombBool 63│12994304│0.0429997 │558751 │ >> ├────────────────┼────────┼──────────┼────────────┤ >> │ 60 combbit 63│5264256 │0.00637439│33556.4 │ >> ├────────────────┼────────┼──────────┼────────────┤ >> │ 60 CombBit 63│5263104 │0.00542141│28533.5 │ >> └────────────────┴────────┴──────────┴────────────┘ >> >> stp 1 >> 60 combbool 64 >> 60 CombBool 64 >> >> ) >> ┌────────────────┬─────────┬────────┬────────────┐ >> │Sentence │Space │Time │Space * Time│ >> ├────────────────┼─────────┼────────┼────────────┤ >> │ 60 combbool 64│285764096│0.735206│2.10095e8 │ >> ├────────────────┼─────────┼────────┼────────────┤ >> │ 60 CombBool 64│214321408│0.729414│1.56329e8 │ >> └────────────────┴─────────┴────────┴────────────┘ >> >> CombBool and CombBit were produced with the J Wicked Toolkit [0] as >> follows, >> >> 'X Y K Z'=. 4 Fetch >> >> CombBool=. [tv f. >> 'K Z'local o ; >> >> K (X <"1@:(-@:i.@:(1 + -~) (|."0 1) 1 {.~ ]) Y) h >> NB. k=. <"1 (-i.1+d=.y-x)|."0 1 y{.1 >> >> Z (X ((-~ $ <@:(0 $~ 0 , ])) , <@:,:@:(0 #~ ])) Y) h >> NB. z=. (d$<(0,y)$0),<,:y#0 >> >> (Z (K ([ +."1&.> ,&.>/\.@:(_1&|."1&.>)@:]) Z) h)^:X >> NB. for. i.x do. z=. k (+."1)&.> ,&.>/\. (_1&|."1)&.> z end. >> >> ; o Z NB. ; z >> ) >> >> 66 Wrap 'CombBool' >> ;@:(3&({::))@:((<@:(2&({::) ([ +."1&.> ,&.>/\.@:(_1&|."1&.>)@:]) 3 >> &({::)) 3} ])^:(0&({::)))@:(<@:(0&({::) ((-~ $ <@:(0 $~ 0 , ])) , >> <@:,:@:(0 #~ ])) 1&({::)) 3} ])@:(<@:(0&({::) <"1@:(-@:i.@:(1 + -~ >> ) (|."0 1) 1 {.~ ]) 1&({::)) 2} ])@:(,&(<;._1 ' K Z')@:;) >> >> >> lshift=.33 b. >> or=.23 b. >> >> 'X Y K Z'=. 4 Fetch >> >> CombBit=. [tv f. >> 'K Z'local o ; >> >> [ assert@:(63 >: Y) NB. assert y<:<:##:_1 (32 b.) 1 >> >> K (X <"0@:(1 lshift~ ] - >:@:i.@:>:@:(-~)) Y) h >> NB. k=.<"0 (y->:i.>:d=:y-x)lshift 1 >> >> Z (X ((<0) ,~ (<i.0) $~ -~) Y) h >> NB. z=. (d$<i.0),<0 >> >> (Z (K ([ or&.> ,&.>/\.@:(_1&lshift&.>)@:]) Z) h)^:X >> NB. for. i.x do. z=. k (or)&.> ,&.>/\. (_1&lshift)&.> z end. >> >> #: o ; o Z NB. #: ;z >> ) >> >> 66 Wrap 'CombBit' >> #:@:;@:(3&({::))@:((<@:(2&({::) ([ 23 b.&.> ,&.>/\.@:(_1&(33 b.)&. >>>)@:]) 3&({::)) 3} ])^:(0&({::)))@:(<@:(0&({::) ((<0) ,~ (<i.0) $~ >> -~) 1&({::)) 3} ])@:(<@:(0&({::) <"0@:((1) 33 b.~ ] - >:@:i.@:>:@ >> :(-~)) 1&({::)) 2} ])@:([ (0 0 $ 13!:8^:((0 e. ])`(12"_)))@:(63 >: >> 1&({::)))@:(,&(<;._1 ' K Z')@:;) >> >> They are mindless transcriptions of combbool and combit. They >> certainly can be simplified but I am resisting the temptation ;) >> >> [0] J Wicked Toolkit >> http://www.2bestsystems.com/foundation/j/Jx.zip >> \Jx\J\J Wicked Toolkit.ijs >> >> >> >> >> >> >> >> >> >> On Fri, Nov 10, 2017 at 6:46 AM, Erling Hellenäs >> <[email protected]> >> wrote: >> >>> Hi all! >>> >>> Bitmap version of comb. Unfortunately handles sets of max 63 items. >>> >>> I tried to make a general version, but hit the problem with #: . >>> >>> ts'5 combbit 10' >>> 3.37831e_5 20864 >>> ts'5 combbool 10' >>> 3.89148e_5 22400 >>> ts'5 combREBoss 10' >>> 5.51649e_5 44416 >>> ts'5 comb 10' >>> 3.76319e_5 50944 >>> >>> ts'13 combbit 26' >>> 0.44835 8.03039e8 >>> ts'13 combbool 26' >>> 0.880373 1.4314e9 >>> ts'13 combREBoss 26' >>> 2.39319 4.22297e9 >>> ts'13 comb 26' >>> 2.59969 4.41693e9 >>> >>> ts'60 combbit 63' >>> 0.00416474 5.26221e6 >>> ts'60 combbool 63' >>> 0.0534253 1.73281e7 >>> ts'60 combREBoss 63' >>> 0.0344776 6.81943e7 >>> ts'60 comb 63' >>> 0.310994 1.38554e8 >>> >>> combbit=: 4 : 0 >>> assert y<:<:##:_1 (32 b.) 1 >>> lshift=.33 b. >>> or=.23 b. >>> k=.<"0 (y->:i.>:d=:y-x)lshift 1 >>> z=. (d$<i.0),<0 >>> for. i.x do. z=. k (or)&.> ,&.>/\. (_1&lshift)&.> z end. >>> #: ;z >>> ) >>> >>> Cheers, >>> >>> Erling Hellenäs >>> >>> >>> --------------------------------------------------------------------- >>> - 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
