Part ot the reason for all the discussion is that the Quora Problem is
ill-defined - as stated in that link,
https://www.quora.com/What-is-total-number-of-positive-integral-solutions-for-x-y-z-such-that-xyz-24
Better:
a) what is the number of sets {x,y,z} such that 24 = */x,y,z, 1 <: x <:
y <: z <: 24 for integers x,y,z
OR
b) what is the number of sets {x,y,z} such that 24 = */x,y,z, 1 < x <:
y <: z < 24 for integers x,y,z
OR
c) what is the number of sets {x,y,z} such that 24 = */x,y,z, 1 < x < y
< z < 24 for integers x,y,z
OR
d) what is the number of sets {x,y,z} such that 24 = */x,y,z, 1 <:
x,y,z <: 24
for integers x,y,z for all permutations of x,y,z
OR
e f g ....
In each case, the requirement is for only the number of sets, not the
sets themselves!
*/ every (3 par 4){each < 2 2 2 3 yields some but not all
permutations for 1 < x,y,x < 24:
(for all our definitions of par, as far as I can see)
6 2 2
2 6 2
2 2 6
4 2 3
2 4 3
4 2 3
so it can't be used directly for any of these enumerations; sorting
rows and taking the nub
yields just
2 2 6
2 3 4
so that the answer to (c) is 2
Similarly, |:/:~~./:~"1 */every (3 par 6){each <1 1 2 2 2 3
1 1 1 1 2 2
1 2 3 4 2 3
24 12 8 6 6 4
so that the answer to (a) is 6, although we find, eg,
#3 parRuskey 6
90
showing that using par-type verbs is not always efficient for the
problem which they
might have envisaged!!!
They're very interesting and pretty important, of course,
cheers,
Mike
etc...
On 03/11/2017 00:15, 'Skip Cave' via Programming 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
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
