[Jprogramming] K-sets - bitmap representation of sets. WAS: Partitions

[Erling Hellenäs]

Hi all!

Comparison

-----Project-----

ts=: 6!:2 , 7!:2@]       NB. Time and space

require 'stats'

NB. Erling Hellenäs

combbool=: 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
)

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
)

NB. Mike Day - non-boxed version

combbitub =: 4 : 0
assert y<:<:##:_1 (32 b.) 1
lshift =.33 b.
or =.23 b.
k =. (y->:ix =. i.>:d=.y-x)lshift 1
z =. ,0
l =. 1#~ #k NB. "box-sizes" as successively 1s, i.#k, triangular nums etc.
for. i.x do.
nz =. _1 lshift z
z =. nz or {.k
for_j. }. i.#k do. NB. tack on the smaller "boxes"
z =. z, (j{k) or (-j{l) {. nz
end.
l =. +/\. l NB. bump up the box sizes
end.
#: z
)

NB. Jose Mario Quintana - J Wicked Toolkit - Tacit versions

". 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')@:;)
)

NB. Linda Alvord - Binary order - Tacit

bitcomb=: 13 :'(x=+/"1 #:i.2^y)#"2#:i.2^y'

NB. Raul Miller - Concise tacit version of combbool

or=. +."1&.>
merge=. ,&.>/\.
shift=. _1&|."1&.>
masks=. -@,. at i.@(1--)  <@|. {.&1@]
start=. (1 ,.@{.~ --1:) <@# ,:@#&0@]

combboolT=: [: ; masks (or merge@:shift)^:(1 + -~/@$@:>@[) start
combboolT=: combboolT f.


x=:1
y=:1
(/:~ x comb y) -: /:~ (x combbool y)#"1 i.y
(/:~ x comb y) -: /:~ (x combbit y)#"1 i.y
(/:~ x comb y) -: /:~ (x combbitub y)#"1 i.y
(/:~ x comb y) -: /:~ (x CombBool y)#"1 i.y
(/:~ x comb y) -: /:~ (x CombBit y)#"1 i.y
(/:~ x comb y) -: /:~ (x bitcomb y)#"1 i.y
(/:~ x comb y) -: /:~ (x combboolT y)#"1 i.y
x=:1
y=:3
(/:~ x comb y) -: /:~ (x combbool y)#"1 i.y
(/:~ x comb y) -: /:~ (x combbit y)#"1 i.y
(/:~ x comb y) -: /:~ (x combbitub y)#"1 i.y
(/:~ x comb y) -: /:~ (x CombBool y)#"1 i.y
(/:~ x comb y) -: /:~ (x CombBit y)#"1 i.y
(/:~ x comb y) -: /:~ (x bitcomb y)#"1 i.y
(/:~ x comb y) -: /:~ (x combboolT y)#"1 i.y
x=:2
y=:2
(/:~ x comb y) -: /:~ (x combbool y)#"1 i.y
(/:~ x comb y) -: /:~ (x combbit y)#"1 i.y
(/:~ x comb y) -: /:~ (x combbitub y)#"1 i.y
(/:~ x comb y) -: /:~ (x CombBool y)#"1 i.y
(/:~ x comb y) -: /:~ (x CombBit y)#"1 i.y
(/:~ x comb y) -: /:~ (x bitcomb y)#"1 i.y
(/:~ x comb y) -: /:~ (x combboolT y)#"1 i.y
x=:2
y=:4
(/:~ x comb y) -: /:~ (x combbool y)#"1 i.y
(/:~ x comb y) -: /:~ (x combbit y)#"1 i.y
(/:~ x comb y) -: /:~ (x combbitub y)#"1 i.y
(/:~ x comb y) -: /:~ (x CombBool y)#"1 i.y
(/:~ x comb y) -: /:~ (x CombBit y)#"1 i.y
(/:~ x comb y) -: /:~ (x bitcomb y)#"1 i.y
(/:~ x comb y) -: /:~ (x combboolT y)#"1 i.y
x=:3
y=:5
(/:~ x comb y) -: /:~ (x combbool y)#"1 i.y
(/:~ x comb y) -: /:~ (x combbit y)#"1 i.y
(/:~ x comb y) -: /:~ (x combbitub y)#"1 i.y
(/:~ x comb y) -: /:~ (x CombBool y)#"1 i.y
(/:~ x comb y) -: /:~ (x CombBit y)#"1 i.y
(/:~ x comb y) -: /:~ (x bitcomb y)#"1 i.y
(/:~ x comb y) -: /:~ (x combboolT y)#"1 i.y

x=:5
y=:10
ts'x combbool y'
ts'x combbit y'
ts'x combbitub y'
ts'x CombBool y'
ts'x CombBit y'
ts'x bitcomb y'
ts'x combboolT y'

x=:12
y=:24
ts'x combbool y'
ts'x combbit y'
ts'x combbitub y'
ts'x CombBool y'
ts'x CombBit y'
ts'x bitcomb y'
ts'x combboolT y'

x=:55
y=:60
ts'x combbool y'
ts'x combbit y'
ts'x combbitub y'
ts'x CombBool y'
ts'x CombBit y'
NB.ts'x bitcomb y' -limit error
ts'x combboolT y'

---Output----



    x=:1
    y=:1
    (/:~ x comb y) -: /:~ (x combbool y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x combbit y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x combbitub y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x CombBool y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x CombBit y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x bitcomb y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x combboolT y)#"1 i.y
1
    x=:1
    y=:3
    (/:~ x comb y) -: /:~ (x combbool y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x combbit y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x combbitub y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x CombBool y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x CombBit y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x bitcomb y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x combboolT y)#"1 i.y
1
    x=:2
    y=:2
    (/:~ x comb y) -: /:~ (x combbool y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x combbit y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x combbitub y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x CombBool y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x CombBit y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x bitcomb y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x combboolT y)#"1 i.y
1
    x=:2
    y=:4
    (/:~ x comb y) -: /:~ (x combbool y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x combbit y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x combbitub y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x CombBool y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x CombBit y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x bitcomb y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x combboolT y)#"1 i.y
1
    x=:3
    y=:5
    (/:~ x comb y) -: /:~ (x combbool y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x combbit y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x combbitub y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x CombBool y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x CombBit y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x bitcomb y)#"1 i.y
1
    (/:~ x comb y) -: /:~ (x combboolT y)#"1 i.y
1

    x=:5
    y=:10
    ts'x combbool y'
3.80595e_5 22528
    ts'x combbit y'
3.20726e_5 21376
    ts'x combbitub y'
5.3882e_5 13824
    ts'x CombBool y'
3.54937e_5 14976
    ts'x CombBit y'
2.43752e_5 15232
    ts'x bitcomb y'
2.73686e_5 50688
    ts'x combboolT y'
3.03621e_5 15744

    x=:12
    y=:24
    ts'x combbool y'
0.206515 2.82336e8
    ts'x combbit y'
0.122897 1.33655e8
    ts'x combbitub y'
0.1078 1.17444e8
    ts'x CombBool y'
0.204538 2.33133e8
    ts'x CombBit y'
0.111325 1.33654e8
    ts'x bitcomb y'
1.19484 1.34218e9
    ts'x combboolT y'
0.204563 2.33135e8

    x=:55
    y=:60
    ts'x combbool y'
4.89082 2.29064e9
    ts'x combbit y'
0.857667 6.75567e8
    ts'x combbitub y'
0.703836 6.71092e8
    ts'x CombBool y'
4.97355 1.71798e9
    ts'x CombBit y'
0.871456 6.75566e8
    NB.ts'x bitcomb y' -limit error
    ts'x combboolT y'
5.06045 1.71798e9

Cheers,

Erling Hellenäs