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
