Hi all !
I analysed Esa Lippus solution. The printout is long, but here is the
code and my explanations.
par2=: 4 : 0
a=.(y#x) #: i. x^y
sort ~.((x=#@~."1 a)#a) </."1 i.y
)
sort=: /:~
3 par2 5
x=:3
y=:5
NB. All combinations of y elements
[a=:(y#x) #: i. x^y
NB. Select the combinations in which the y elements
NB. are distributed over x buckets
[v=: ((x=#@~."1 a)#a)
NB. Pack the elements in each bucket combination.
[w=:v </."1 i.y
NB. Sort to display nicely
sort ~. w
Cheers,
Erling Hellenäs
Den 2017-10-26 kl. 07:07, skrev 'Skip Cave' via Programming:
Lippu,
Yes, your par2 is MUCH faster than Raul's nparts. If I have some time, I
will put together a time/space test for all the proposed solutions.
Skip
Skip Cave
Cave Consulting LLC
On Wed, Oct 25, 2017 at 1:58 PM, Lippu Esa <[email protected]> wrote:
Hello,
I get the following with the partition verb I posted last Thursday (J8.06
and 4 core 2.9GHz CPU and 16GB RAM):
par2=: 4 : 0
a=.(y#x) #: i. x^y
sort ~.((x=#@~."1 a)#a) </."1 i.y
)
ts '#5 par2 8'
4.15977615 151821824
ts '# 6 par2 8'
2.55073168 358252032
Esa
-----Original Message-----
From: Programming [mailto:[email protected]] On
Behalf Of 'Skip Cave' via Programming
Sent: Wednesday, October 25, 2017 8:12 PM
To: [email protected]
Subject: Re: [Jprogramming] Partitions
Raul got it right with his nparts verb. In my original example of par, I
constructed the required output of par by hand. In that process, I
overlooked the majority of the possible combinations of the ways that 5
items could be separated into 3 containers. That caused confusion in the
various attempts to implement what I proposed. I wasn't very thorough in
vetting my example output, and Mike valiantly tried to point out the flaws
in my proposal. Raul showed how much I missed clearly in my par example
when he demonstrated:
#3 nparts 5
25
#3 par 5
6
Rob also pointed out the issue in his posts. Erling's v7 verb got to the
same result as Raul's nparts.
The number of possible partitions of n objects grows rapidly with n:
#3 nparts 5
25
#3 nparts 6
90
#3 nparts 7
301
#3 nparts 8
966
Increasing the number of partitions reduces the number of combinations but
significantly increases execution time with Raul's nparts :
#4 nparts 8
1701
#5 nparts 8
1050
#6 nparts 8
266
The 5 #nparts 8 took over 30 seconds to run on my i7 laptop. The #6 nparts
8 took about 3 minutes.
Is there a more computationally efficient way to calculate the partitions?
Skip
----------------------------------------------------------------------
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
