The verb combboolT is neat. Yet, this seems to be another one of those cases where relative terseness does not necessarily imply relative outperformance.
On Sun, Nov 12, 2017 at 1:32 AM, Raul Miller <[email protected]> wrote: > 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
