Hmm... actually, thinking about it, the par approach here is not efficient enough for this example. 5 parRuskeyE 32 is too big of a result, I think. (358358 has 5 distinct prime factors and, thus, 32 integer factors.)
So, ok, we can do another pass at this problem. (But, also, this should be a caution about trying to generalize - an approach which solves a problem and which solves a generalization of that problem will quite often be useless for an instance of a different generalization of that problem.) Thanks, -- Raul On Fri, Nov 3, 2017 at 3:00 AM, Raul Miller <[email protected]> wrote: > Sure - and I think we have addressed that (parRuskyE by Erling > Hellenäs being possibly the best implementation) - I was just pointing > out the differences between this problem statement and the quora > question which inspired it. > > Thanks, > > -- > Raul > > On Fri, Nov 3, 2017 at 1:10 AM, 'Skip Cave' via Programming > <[email protected]> wrote: >> Raul, >> >> Here's another try to state the rules of this problem:of the n objects >> >> I have n objects. Each object has a single numeric value. >> More than one object can have the same numeric value. >> The "containers" I talk about must each contain one or more of the objects. >> The "value" of each specific container is obtained by multiplying together >> the numeric values of all the objects in that container. >> The value of the complete set of containers is "p" and p is found by >> multiplying together all the values in each container. >> >> The order of objects in a container does not change the value of the >> container, and the order of containers with the same objects in them do not >> consist of a new configuration. >> >> So here's the problem I was trying to solve: >> >> given a set of variables x1, x2, x3, x4.... xn >> >> Show all the different sets of x1 - xn that solves the equality: >> p = */ x1, x2, x3, x4, ....xn >> >> All permutations of the same set of x1-xn is considered the same solution >> >> The "unique objects" I describe are really the factors of some integer. An >> example question: >> >> 358358=*/x1, x2, x3, x4, x5 >> How many different combinations of 5 integersx1, x2, x3, x4, x5 solve this >> equality? (Different orders don't count) >> >> What about: >> 358360=*/x1, x2, x3, x4, x5 ? >> >> Skip >> >> Skip Cave >> Cave Consulting LLC >> >> On Thu, Nov 2, 2017 at 7:54 PM, Raul Miller <[email protected]> wrote: >> >>> Since that problem is so small, it would be tempting to just brute >>> force it. (Build out all copies of 3 integers, 1 .. 24 and then select >>> those whose product is 24. That's less than 2 million tests, so a >>> computer can run through them in a fraction of a second.) >>> >>> Though, as other posters on that quora page have noted, the question >>> is ambiguous. (is x=1, y=2, z=12 the same as x=12, y=1, z=2? Why or >>> why not?) >>> >>> So to be thorough, you sort of have to supply answers for "x is a >>> different variable from y and z" and "it does not really matter which >>> variable you use for whichever integer". And, since the problem is >>> small, it's trivial to go from the permutations answer to the >>> combinations answer: >>> >>> #(#~ 24 = */"1)1+24 24 24 #:i.24^3 >>> 30 >>> #~./:~"1(#~ 24 = */"1)1+24 24 24 #:i.24^3 >>> 6 >>> >>> Still... fun problem. >>> >>> Thanks, >>> >>> -- >>> Raul >>> >>> >>> On Thu, Nov 2, 2017 at 8:15 PM, 'Skip Cave' via Programming >>> <[email protected]> wrote: >>> > 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 >>> ---------------------------------------------------------------------- >>> 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
