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
