Hi all !
My partition projects are parRuskeyE, parE and parE2.
parRuskeyE
Frank Ruskeys algorithm, now with massively parallel recursion.
parE
Similar to parELMDE, but works with bitmaps and creates less combinations.
parE2
Creates unique bucket groups, combines the buckets within each bucket group
with sets of combinations with the correct number of items.
Combinations are filtered to avoid duplication.
Performance
ParRuskeyE is the winner in performance with parE not far behind.
They can all handle high x combined with high y.
x=:5
y=:7
ts'x parRuskeyE y'
0.000265134 127232
ts'x parE y'
0.000889053 794496
ts'x parE2 y'
0.00687637 217600
x=:5
y=:10
ts'x parRuskeyE y'
0.0683502 3.8954e7
ts'x parE y'
0.224765 1.70531e8
ts'x parE2 y'
1.50793 6.50278e7
x=:9
y=:10
ts'x parRuskeyE y'
0.00013385 75136
ts'x parE y'
0.0668154 5.03395e7
ts'x parE2 y'
0.0767498 5.86112e6
You can see the programs below.
Cheers,
Erling Hellenäs
---Project---
NB. parRuskeyE
parRuskeyE =: 4 : 0
r=. (,: i.y) SE (x-1);y-1
r </."1 i.y
)
SE =: 4 : 0
'k n' =. y
r=. (0,_1{.$x)$0
if. k=n do.
r=.x
else.
s=.n {."1 x
e=.(n+1)}."1 x
a=.,/s ( [,"1 1 (i.k+1),"0 1 ])"1 e
r=.r, a SE k;n-1
if. k > 0 do.
a=.s,.k,.e
r=.r, a SE (k-1);n-1
end.
end.
r
)
NB. parE
combE=: 4 : 0
u=:(-y){.i.x-1
w=:(y#x)-u+|.u
o=:u <@([+[:i.])"0 w
p=:>([:,/[,"0 1 "0 _] )&.>/ (}:o),<,.>{:o
)
parE=: 4 : 0
NB. Assume a table with x rows and y columns.
NB. Each row is a bucket, each column an item.
NB. Two buckets can not contain the same item.
NB. This means there can only be one item in each column.
NB. Each column can be rotated in x ways.
NB. Generate all combinations of the possible rotations
NB. except for the first and last x-1 columns.
o=: x combE y
NB. Pick the rotation from a bitmap where each
NB. row is a possible rotation
NB. We now have a three-dimensional bitmap of
NB. combination, items in the bucket and bucket
NB. True means the bucket contains the corresponding item
v=:o{(i.x)|."0 1 x{.1
NB. Select the combination where each bucket contains at least
NB. one item.
b=:(*./"1+./"2 v)#v
NB. Reorder the dimensions
NB. Now they are combination, bucket and items in the bucket.
c=:0 2 1|:b
NB. Sort the buckets within the combinations so that
NB. buckets with the same contents also are in the same place
NB. in bucket order
d=:/:~"2 c
NB. Remove duplicates
e=: ~.d
NB. Display
e<@# i.y
)
NB. parE2
NB. All combinations of y items
combE2=: 3 : 'm{.#:i.m=.(0~:#y)*<.2^y'
NB. Select from y where there are no item duplicates in the buckets of x
NB. and the buckets of y.
filter=: 4 : '(x -.@:(+./)@:*.&(+./)"2 y)#y'
NB. Cartesian product
NB. If y is empty after filter the result will be empty
cpE=: 4 : 'x,"2 y'
NB. The argument is a boxed array of combinations
NB. Combine each combination in the last box with all combinations in
box two
NB. from the right.
NB. Continue until all box contents are combined.
NB. BUT - Filter the incoming combinations before the cartesian product
NB. AND - AFTER the cartesian product -
NB. -Sort the buckets in each bucket combination to get equal bucket
combinations in
NB. the same bucket number.
NB. -Remove duplicates.
filterMerge=:[: > [: ([: ~.@:(/:~"2)@:; <"2@:] ([ cpE [ filter ])&.>
<@:[)&.>/ ]
bCombE=: 4 :0
NB. All combinations of bucket sizes
NB. Which sum to y
v=.1+y-x
p=.>:(x#v)#:i.v^x
r=.(y= +/"1 p)#p
NB. sort them in size order
t=./:~"1 r
NB. Remove duplicates
~. t
)
parE2=: 4 : 0
NB. All combinations of all items
v=.}.combE2 y
NB.All unique combinations of x buckets with y items
b=.x bCombE y
NB. Unique bucket sizes in all bucket combinations
c=. ~. ,b
NB. Number of items in each combination
d=.+/"1 v
NB. Remove unneded combinations
q=: d e.c
v1=: q#v
d1=: q#d
NB. Insert a bucket dimension. The dimensions are now
NB. bucket combination, bucket and item combination in the bucket
v2=.((#v1),1,y)$,v1
NB. Pack sets of combinations with number of items corresponding to
NB. the bucket sizes in the classes in c1
w=.d1</.v2
c1=. ~.d1
NB. For all bucket combinations, pack the boxes with the corresponding
NB. number of items and run filterMerge on them
f=. 4 : 'filterMerge x{y'
v32=. ;(<"1 c1 i.b) f&.><w
NB. Select combinations with one and only one of each number
v4=.(1=*/"1 +/"2 v32) # v32
NB. Pack
v4 <@# i.y
)
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
