Hi all!
Here is a reference to Knuth, and descriptions of how to enumerate these
set partitions:
https://math.stackexchange.com/questions/222780/enumeration-of-partitions
There are solutions:
http://www.informatik.uni-ulm.de/ni/Lehre/WS03/DMM/Software/partitions.pdf
https://blogs.msdn.microsoft.com/oldnewthing/20140324-00/?p=1413
https://codereview.stackexchange.com/questions/1526/finding-all-k-subset-partitions/1944#1944
Cheers,
Erling Hellenäs
On 2017-10-28 19:06, Erling Hellenäs wrote:
Hi all !
I tried to analyse Mikes version.
--- Project ---
parMD=: 4 : 0
a =. ~. i.~"1 iy #: i. */ iy =. >: i.y
a =. a#~ x = #@~."1 a
sort a </."1 i. y
)
sort=: /:~
2 parMD 4
x=:2
y=:4
NB.
[iy =: >: i.y
[v=: i. */ iy
NB. You put item 0 in class 0. Now you can put item 1 there also
NB. or you start a new class 1. You can put item y in class 0 to y.
NB. This is the formula for that. Generating !y items.
[w=: iy #: v
NB. Normalize the class names so that a class starting in column n
always have name n
NB. Example: Combinations with three items in class 0 and the forth in
class 1, 2 or 3 are equal.
NB. The second class gets the name 3 since it starts in column 3
[o=:i.~"1 w
NB. Remove class combinations which are equal.
[a=: ~. o
NB. Select the class combinations with x different classes.
[a =. a#~ x = #@~."1 a
NB. Pack the items in the boxes
[p=:a </."1 i. y
NB.Sort to display nicely.
[sort p
---Output---
2 parMD 4
┌─────┬─────┐
│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 │
└─────┴─────┘
x=:2
y=:4
NB.
[iy =: >: i.y
1 2 3 4
[v=: i. */ iy
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
NB. You put item 0 in class 0. Now you can put item 1 there also
NB. or you start a new class 1. You can put item y in class 0 to y.
NB. This is the formula for that. Generating !y items.
[w=: iy #: v
0 0 0 0
0 0 0 1
0 0 0 2
0 0 0 3
0 0 1 0
0 0 1 1
0 0 1 2
0 0 1 3
0 0 2 0
0 0 2 1
0 0 2 2
0 0 2 3
0 1 0 0
0 1 0 1
0 1 0 2
0 1 0 3
0 1 1 0
0 1 1 1
0 1 1 2
0 1 1 3
0 1 2 0
0 1 2 1
0 1 2 2
0 1 2 3
NB. Normalize the class names so that a class starting in column n
always have name n
NB. Example: Combinations with three items in class 0 and the forth
in class 1, 2 or 3 are equal.
NB. The second class gets the name 3 since it starts in
column 3
[o=:i.~"1 w
0 0 0 0
0 0 0 3
0 0 0 3
0 0 0 3
0 0 2 0
0 0 2 2
0 0 2 3
0 0 2 3
0 0 2 0
0 0 2 3
0 0 2 2
0 0 2 3
0 1 0 0
0 1 0 1
0 1 0 3
0 1 0 3
0 1 1 0
0 1 1 1
0 1 1 3
0 1 1 3
0 1 2 0
0 1 2 1
0 1 2 2
0 1 2 3
NB. Remove class combinations which are equal.
[a=: ~. o
0 0 0 0
0 0 0 3
0 0 2 0
0 0 2 2
0 0 2 3
0 1 0 0
0 1 0 1
0 1 0 3
0 1 1 0
0 1 1 1
0 1 1 3
0 1 2 0
0 1 2 1
0 1 2 2
0 1 2 3
NB. Select the class combinations with x different classes.
[a =. a#~ x = #@~."1 a
0 0 0 3
0 0 2 0
0 0 2 2
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
NB. Pack the items in the boxes
[p=:a </."1 i. 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│
└─────┴─────┘
NB.Sort to display nicely.
[sort p
┌─────┬─────┐
│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 │
└─────┴─────┘
Cheers,
Erling Hellenäs
On 2017-10-28 17:08, 'Mike Day' via Programming wrote:
Thanks for the update, Erling. I’m looking for a constructive
approach, which is perhaps what Raul has been exploring. It
probably won’t improve matters, if ever I get my head round it. I
won’t have access to email for another 24 hours or so, so don’t hold
your breath! Meanwhile, I’m pleased with the speed-up that you’ve
confirmed for my modifications for some problem sizes.
Cheers,
Mike
Please reply to [email protected].
Sent from my iPad
On 28 Oct 2017, at 13:39, Erling Hellenäs <[email protected]>
wrote:
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
----------------------------------------------------------------------
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
