So... 358358 has five prime factors (32 integer factors). We want to
find all sorted sequences (not sets - values can repeat) of five of
those factors whose product is 358358.
To restrict our search, we can investigate only those sorted sequences
of "number of prime factors represented in the variable" whose sum is
five:
~./:~"1 (#~ 5=+/"1) 6 #.inv i.6^5
0 0 0 0 5
0 0 0 1 4
0 0 0 2 3
0 0 1 1 3
0 0 1 2 2
0 1 1 1 2
1 1 1 1 1
In other words, the results of these seven expressions (use
require'stats' first to get comb):
1 1 1 1 358358
(1 1 1,(358358%*/),*/)"1 (4 comb 5){q:358358
/:~"1 (1 1 1,(358358%*/),*/)"1 (3 comb 5){q:358358
/:~"1 (1 1,q:@(358358%*/),*/)"1 (3 comb 5){q:358358
~./:~"1 (1 1,({.,*/@}.)@q:@(358358%*/),*/)"1 (2 comb 5){q:358358
/:~"1 (1,q:@(358358%*/),*/)"1 (2 comb 5){q:358358
q:358358
That's 44 different solutions:
1 1 1 1 358358
1 1 1 179 2002
1 1 1 13 27566
1 1 1 11 32578
1 1 1 7 51194
1 1 1 2 179179
1 1 1 154 2327
1 1 1 182 1969
1 1 1 143 2506
1 1 1 286 1253
1 1 1 91 3938
1 1 1 77 4654
1 1 1 358 1001
1 1 1 26 13783
1 1 1 22 16289
1 1 1 14 25597
1 1 13 154 179
1 1 11 179 182
1 1 11 13 2506
1 1 7 179 286
1 1 7 13 3938
1 1 7 11 4654
1 1 2 179 1001
1 1 2 13 13783
1 1 2 11 16289
1 1 2 7 25597
1 1 11 14 2327
1 1 7 22 2327
1 1 7 26 1969
1 1 7 143 358
1 1 2 77 2327
1 1 2 91 1969
1 1 2 143 1253
1 11 13 14 179
1 7 13 22 179
1 7 11 26 179
1 7 11 13 358
1 2 13 77 179
1 2 11 91 179
1 2 11 13 1253
1 2 7 143 179
1 2 7 13 1969
1 2 7 11 2327
2 7 11 13 179
We could of course come up with a routine which does something similar
for other examples (but we will run into prohibitive resource
limitations if we allow large enough integers).
So... just to confirm... this is the problem we are trying to solve?
Thanks,
--
Raul
On Fri, Nov 3, 2017 at 3:14 AM, Raul Miller <[email protected]> wrote:
> 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
