Wow! I'm amazed at the response my partition problem got on the programming forum. I have learned quite a lot about various ways to optimize a combination verb, as well as the partition verb.
I think that it might be good to look at the original problem that caused me to come up with the partition solution: I was trying to solve a Quora problem that asks: What is total number of positive integer solutions for (x, y, z) such that xyz=24? <https://www.quora.com/What-is-total-number-of-positive-integral-solutions-for-x-y-z-such-that-xyz-24> I wanted to eventually generalize the problem to handle a list of n integers whose product [image: \prod] or +/ is equal to integer p. so given the equation [image: \prod] (x1, x2, x3, ... xn ) = p What is total number of positive integer solutions sets for x1, x2,x3 ...xn? So for our original problem first we need to factor the number: q:24 2 2 2 3 - these are the factors of 24. A reasonable way to solve this is to build a function that will find all the ways to partition the list of factors into three groups: ]a =.3 par 4 ┌───┬───┬───┐ │0 1│2 │3 │ ├───┼───┼───┤ │0 2│1 │3 │ ├───┼───┼───┤ │0 │1 2│3 │ ├───┼───┼───┤ │0 3│1 │2 │ ├───┼───┼───┤ │0 │1 3│2 │ ├───┼───┼───┤ │0 │1 │2 3│ └───┴───┴───┘ Now replace the indices with the actual prime factors of 24 ]b =. a cvt q:24 ┌───┬───┬───┐ │2 2│2 │3 │ ├───┼───┼───┤ │2 2│2 │3 │ ├───┼───┼───┤ │2 │2 2│3 │ ├───┼───┼───┤ │2 3│2 │2 │ ├───┼───┼───┤ │2 │2 3│2 │ ├───┼───┼───┤ │2 │2 │2 3│ └───┴───┴───┘ ]c=. */ each b ┌─┬─┬─┐ │4│2│3│ ├─┼─┼─┤ │4│2│3│ ├─┼─┼─┤ │2│4│3│ ├─┼─┼─┤ │6│2│2│ ├─┼─┼─┤ │2│6│2│ ├─┼─┼─┤ │2│2│6│ └─┴─┴─┘ Now sort the lists and get rid of the copies: ~. c/:"1 c ┌─┬─┬─┐ │2│3│4│ ├─┼─┼─┤ │2│2│6│ └─┴─┴─┘ So the answer to the question: What is total number of positive integer solutions for (x, y, z) such that xyz=24? <https://www.quora.com/What-is-total-number-of-positive-integral-solutions-for-x-y-z-such-that-xyz-24> is: 2 3 4, & 2 2 6 So now can we build a generalized verb that does it all in one step for any n? 3 list 24 2 3 4 2 2 6 Skip Skip Cave Cave Consulting LLC On Thu, Nov 2, 2017 at 5:32 PM, Raul Miller <[email protected]> wrote: > Oops, no... the 1 partition results are not from comb, and 1 comb y > won't get them. > > I was just using ,.< i.y > > And, the 2 partition results were also not from comb, I was using > > ((y#2)#:"1 0 }.i.2^y-1) </."1 i.y > > Still... tends to be faster than parRuskeyE. > > Sorry about that, I'm just waking up from a nap... > > Thanks, > > -- > Raul > > > On Thu, Nov 2, 2017 at 6:29 PM, Raul Miller <[email protected]> wrote: > > The performance of your parRuskeyE is looking really nice. > > > > That said, for 1 or 2 partitions, a comb based approach (using the > > comb from require'stats') is still tends to be significantly faster > > (except for 2 parRuskeyE 2). (And, once the number of values in a > > partition has reached like 13 or 14, this speed advantage starts > > creeping into results involving more partitions, but it's not a factor > > of 2 speed advantage for any practical result size so it's probably > > not worrying about.) > > > > The 1 partition results would be trivial to incorporate - it's just > > <"1]1 comb y where y is the number of partitions. > > > > Thanks, > > > > -- > > Raul > > > > > > On Thu, Nov 2, 2017 at 9:28 AM, Erling Hellenäs > > <[email protected]> wrote: > >> 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 > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
