Hi all !
Current state with Mike Days modification of Esa Lippus algorithm.I
managed to improve my version.
--- Project ...
ts=: 6!:2 , 7!:2@] NB. Time and space
normalize=: 3 :0
NB. The idea here is to normalize the representation so that
NB. the copies are adjacent.
NB. Sort buckets within each combination after first item in each bucket
v31=.(] /: {.&.>)"1 y
NB. Sort buckets within each combination after number of items in each
bucket
v4=.(] /: #&.>)"1 v31
NB. Sort
/:~ v4
)
compare=: -:&:normalize
NB. Esa Lippu
parEL=: 4 : 0
a=.(y#x) #: i. x^y
sort ~.((x=#@~."1 a)#a) </."1 i.y
)
NB. Raul
parR=: (#~ 1 - a: e."1 ])@~.@([: /:~"1 i.@] </."1~ [ #.^:_1 [ i.@^ ])
NB. Erling
NB. All combinations of y item
combE2=: 3 : 'm{.#:i.m=.(0~:#y)*<.2^y'
NB. Cartesian product
cpE=: 4 : ',/x ,"2 "2 _ y'
parE =: 4 : 0
NB. All combinations of all items
v=.}.combE2 y
NB. Select combinations with less than or equal to 1+y-x items
v1=.((+/"1 v)<:1+y-x)#v
NB. All combinations in all buckets
v11=.((#v1),1,y)$,v1
v21=.>cp&.>/x#<v11
NB. Select combinations with one and only one of each number
v3=.(1=*/"1 +/"2 v21) # v21
NB. The idea here is to normalize the representation so that
NB. the copies are adjacent.
NB. Sort buckets within each combination
v31=./:~"2 v3
NB. Remove duplicates
v4=. ~.v31
NB. Pack
v4 <@# i.y
)
NB. Mike Day modification of Esa Lippu algorithm
parMD =: 4 : 0
a =. ~. i.~"1 iy #: i. */ iy =. >: i.y
a =. a#~ x = #@~."1 a
sort a </."1 i. y
)
---Printout---
x=:1
y=:1
[EL=:x parEL y
┌─┐
│0│
└─┘
[R=:x parR y
┌─┐
│0│
└─┘
[E=:x parE y
┌─┐
│0│
└─┘
[MD=:x parMD y
┌─┐
│0│
└─┘
EL compare R
1
EL compare E
1
EL compare MD
1
x=:1
y=:2
[EL=:x parEL y
┌───┐
│0 1│
└───┘
NB.[R=:x parR y - Length Error
[E=:x parE y
┌───┐
│0 1│
└───┘
[MD=:x parMD y
┌───┐
│0 1│
└───┘
EL compare R
0
EL compare E
1
EL compare MD
1
x=:1
y=:3
[EL=:x parEL y
┌─────┐
│0 1 2│
└─────┘
NB. R=:x parR y - Length Error
[E=:x parE y
┌─────┐
│0 1 2│
└─────┘
[MD=:x parMD y
┌─────┐
│0 1 2│
└─────┘
EL compare R
0
EL compare E
1
EL compare MD
1
x=:2
y=:4
[EL=:x parEL y
┌─────┬─────┐
│0 │1 2 3│
├─────┼─────┤
│0 1 │2 3 │
├─────┼─────┤
│0 1 2│3 │
├─────┼─────┤
│0 1 3│2 │
├─────┼─────┤
│0 2 │1 3 │
├─────┼─────┤
│0 2 3│1 │
├─────┼─────┤
│0 3 │1 2 │
└─────┴─────┘
[R=:x parR y
┌─────┬─────┐
│0 1 2│3 │
├─────┼─────┤
│0 1 3│2 │
├─────┼─────┤
│0 1 │2 3 │
├─────┼─────┤
│0 2 3│1 │
├─────┼─────┤
│0 2 │1 3 │
├─────┼─────┤
│0 3 │1 2 │
├─────┼─────┤
│0 │1 2 3│
└─────┴─────┘
[E=:x parE y
┌─────┬─────┐
│3 │0 1 2│
├─────┼─────┤
│2 │0 1 3│
├─────┼─────┤
│2 3 │0 1 │
├─────┼─────┤
│1 │0 2 3│
├─────┼─────┤
│1 3 │0 2 │
├─────┼─────┤
│1 2 │0 3 │
├─────┼─────┤
│1 2 3│0 │
└─────┴─────┘
[MD=:x parMD y
┌─────┬─────┐
│0 │1 2 3│
├─────┼─────┤
│0 1 │2 3 │
├─────┼─────┤
│0 1 2│3 │
├─────┼─────┤
│0 1 3│2 │
├─────┼─────┤
│0 2 │1 3 │
├─────┼─────┤
│0 2 3│1 │
├─────┼─────┤
│0 3 │1 2 │
└─────┴─────┘
EL compare R
1
EL compare E
1
EL compare MD
1
x=:2
y=:5
EL=:x parEL y
R=:x parR y
E=:x parE y
MD=:x parMD y
EL compare R
1
EL compare E
1
EL compare MD
1
x=:3
y=:5
EL=:x parEL y
R=:x parR y
E=:x parE y
MD=:x parMD y
EL compare R
1
EL compare E
1
EL compare MD
1
x=:3
y=:6
EL=:x parEL y
R=:x parR y
E=:x parE y
MD=:x parMD y
EL compare R
1
EL compare E
1
EL compare MD
1
ts'x parEL y'
0.00251336 403840
ts'x parR y'
0.00441964 465280
ts'x parE y'
0.0162486 2.33524e7
ts'x parMD y'
0.000315755 224640
Cheers,
Erling
On 2017-10-28 06:35, Lippu Esa wrote:
Hi Mike,
Thank you for the improvements. And thanks to Erling for comments and analysis.
Esa
-----Original Message-----
From: Programming [mailto:[email protected]] On Behalf
Of 'Mike Day' via Programming
Sent: Friday, October 27, 2017 2:26 PM
To: [email protected]
Subject: Re: [Jprogramming] Partitions
Sorry, I haven’t got a useful direct response for Raul’s comment on this.
BUT, here are a couple of amendments which seem to greatly improve on Lippu
Esa’s par2.
The main improvement hangs on the observation that rows in a such as
000102 and 000201 (spaces removed) are essentially the same. This identity
can be exposed by means of i.~ , which returns 000305 for each of these
examples.
See “mdpart”
Some further improvement arises from using a compound base, 1 2 3 ... instead
of x
in the #: expression, as exploited in “mdpart1”
I’m copying from an iPad script (!!!), so apologies if it looks strange. I’m
away from home, and emails from the laptop are inconvenient.
This is the script:
<<
NB. new file created
mdpart =: 4 : 0
NB. after Lippu Esa's 'par2'
NB. The key improvement is doing ~. on i.~"1 applied to a
NB. Also, column 0 is all zero
NB. tacit definition of array a:
NB. a =. x ([ (] #~ (= #@~."1)) #~ ~.@:(i.~"1)@:(0,.#:) i.@^) <: y
NB. More explicit form of definition of a:
a =. ~. i.~"1 ] 0,. (ym1#x) #: i. x^ ym1 =. y - 1
a =. a#~ x = #@~."1 a
NB. There's no need now to seek the nub of the boxed output:
sort a </."1 i. y
)
mdpart1 =: 4 : 0
NB. after 'mdpart'
NB. use >: i. y instead of x as base for #:
a =. ~. i.~"1 iy #: i. */ iy =. >: i.y
a =. a#~ x = #@~."1 a
NB. you can save memory for slightly more runtime by swapping the filters:
NB. a =. iy #: i. */ iy =. >: i.y
NB. a =. ~. i.~"1 a#~ x = #@~."1 a
NB. There's no need now to seek the nub of the boxed output:
sort a </."1 i. y
)
end of script
Snips from ‘terminal’ - sorry, I don’t know how to force fixed width!
|:2 mdpart 5
+-------+-----+-----+-------+-------+-----+-------+-----+-----+-----+-------+-----+-----+-----+-----+
|0 |0 1 |0 1 2|0 1 2 3|0 1 2 4|0 1 3|0 1 3 4|0 1 4|0 2 |0 2 3|0 2 3 4|0
2 4|0 3 |0 3 4|0 4 |
+-------+-----+-----+-------+-------+-----+-------+-----+-----+-----+-------+-----+-----+-----+-----+
|1 2 3 4|2 3 4|3 4 |4 |3 |2 4 |2 |2 3 |1 3 4|1 4 |1 |1
3 |1 2 4|1 2 |1 2 3|
+-------+-----+-----+-------+-------+-----+-------+-----+-----+-----+-------+-----+-----+-----+-----+
ts
6!:2 , 7!:2@]
(par2 -: mdpart) / 3 5
1
(par2 -: mdpart) / 3 5
1
(par2 -: mdpart) / 5 8
1
(mdpart -: mdpart1) / 5 8
1
ts'mdpart/ 5 8'
0.067471 3.67081e7
ts'mdpart1/ 5 8'. NB. faster here too!
0.035821 1.41636e7
ts'par2/ 5 8'. NB. Somewhat slower
12.1893 1.64228e8
Cheers,
Mike
Please reply to [email protected].
Sent from my iPad
On 26 Oct 2017, at 16:11, Mike Day <[email protected]> wrote:
I was looking at par2 earlier today, with a view to making it tacit, and
noticed that removing duplicate solutions with ~. greatly increases the running
time. I suppose that’s because the array is boxed. Doing ~. after the sort
doesn’t help.
Limited tests suggest the tacit version’s performance is similar to that for
the explicit one.
Mike
Please reply to [email protected].
Sent from my iPad
On 26 Oct 2017, at 09:55, Erling Hellenäs <[email protected]> wrote:
Hi all !
The last comment should be:
NB. Select the unique combinations. Sort to display nicely
sort ~. w
Cheers,
Erling
Den 2017-10-26 kl. 10:38, skrev Erling Hellenäs:
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
----------------------------------------------------------------------
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
