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
