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
