Hi all !
You want to factorize a number. If there are less factors than n, you
can't solve the problem ?
If there are more factors you want to multiply factors to get n left?
You want to enumerate the possible factor combinations?
The factors have to be unique? 20 = 2 *2 * 5 has the two factors 4 and 5 ?
For n=5 there is no solution, for n=2 there is one solution, 4 5?
1 is considered a factor? A number is considered a factor of itself?
21945 = */3 5 7 11 19 has several solutions for n=3, those below?
You possibly have to sort and filter them to make sure they are unique?
[a=:3 parRuskeyE 5
┌─────┬─────┬─────┐
│0 3 4│1 │2 │
├─────┼─────┼─────┤
│0 4 │1 3 │2 │
├─────┼─────┼─────┤
│0 4 │1 │2 3 │
├─────┼─────┼─────┤
│0 2 4│1 │3 │
├─────┼─────┼─────┤
│0 4 │1 2 │3 │
├─────┼─────┼─────┤
│0 1 4│2 │3 │
├─────┼─────┼─────┤
│0 3 │1 4 │2 │
├─────┼─────┼─────┤
│0 │1 3 4│2 │
├─────┼─────┼─────┤
│0 │1 4 │2 3 │
├─────┼─────┼─────┤
│0 2 │1 4 │3 │
├─────┼─────┼─────┤
│0 │1 2 4│3 │
├─────┼─────┼─────┤
│0 1 │2 4 │3 │
├─────┼─────┼─────┤
│0 3 │1 │2 4 │
├─────┼─────┼─────┤
│0 │1 3 │2 4 │
├─────┼─────┼─────┤
│0 │1 │2 3 4│
├─────┼─────┼─────┤
│0 2 │1 │3 4 │
├─────┼─────┼─────┤
│0 │1 2 │3 4 │
├─────┼─────┼─────┤
│0 1 │2 │3 4 │
├─────┼─────┼─────┤
│0 2 3│1 │4 │
├─────┼─────┼─────┤
│0 3 │1 2 │4 │
├─────┼─────┼─────┤
│0 1 3│2 │4 │
├─────┼─────┼─────┤
│0 2 │1 3 │4 │
├─────┼─────┼─────┤
│0 │1 2 3│4 │
├─────┼─────┼─────┤
│0 1 │2 3 │4 │
├─────┼─────┼─────┤
│0 1 2│3 │4 │
└─────┴─────┴─────┘
[r=:a (*/)@:{&.>"1 0 < 3 5 7 11 19
┌───┬────┬────┐
│627│5 │7 │
├───┼────┼────┤
│57 │55 │7 │
├───┼────┼────┤
│57 │5 │77 │
├───┼────┼────┤
│399│5 │11 │
├───┼────┼────┤
│57 │35 │11 │
├───┼────┼────┤
│285│7 │11 │
├───┼────┼────┤
│33 │95 │7 │
├───┼────┼────┤
│3 │1045│7 │
├───┼────┼────┤
│3 │95 │77 │
├───┼────┼────┤
│21 │95 │11 │
├───┼────┼────┤
│3 │665 │11 │
├───┼────┼────┤
│15 │133 │11 │
├───┼────┼────┤
│33 │5 │133 │
├───┼────┼────┤
│3 │55 │133 │
├───┼────┼────┤
│3 │5 │1463│
├───┼────┼────┤
│21 │5 │209 │
├───┼────┼────┤
│3 │35 │209 │
├───┼────┼────┤
│15 │7 │209 │
├───┼────┼────┤
│231│5 │19 │
├───┼────┼────┤
│33 │35 │19 │
├───┼────┼────┤
│165│7 │19 │
├───┼────┼────┤
│21 │55 │19 │
├───┼────┼────┤
│3 │385 │19 │
├───┼────┼────┤
│15 │77 │19 │
├───┼────┼────┤
│105│11 │19 │
└───┴────┴────┘
Of the problem remains how to factorize and putting it all together?
Cheers,
Erling Hellenäs
Den 2017-11-03 kl. 06:10, skrev 'Skip Cave' via Programming:
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
