[Jprogramming] Partitions
'Mike Day' via Programming
programming at jsoftware.com
Sat Oct 28 15:08:14 UTC 2017
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 mike_liz.day at tiscali.co.uk.
Sent from my iPad
> On 28 Oct 2017, at 13:39, Erling Hellenäs <erling at erlinghellenas.se> 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:programming-bounces at forums.jsoftware.com] On Behalf Of 'Mike Day' via Programming
>> Sent: Friday, October 27, 2017 2:26 PM
>> To: programming at jsoftware.com
>> 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 mike_liz.day at tiscali.co.uk.
>> Sent from my iPad
>>
>>> On 26 Oct 2017, at 16:11, Mike Day <mike_liz.day at tiscali.co.uk> 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 mike_liz.day at tiscali.co.uk.
>>> Sent from my iPad
>>>
>>>> On 26 Oct 2017, at 09:55, Erling Hellenäs <erling at erlinghellenas.se> 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 <Esa.Lippu at varma.fi> 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:programming-bounces at forums.jsoftware.com] On
>>>>>>> Behalf Of 'Skip Cave' via Programming
>>>>>>> Sent: Wednesday, October 25, 2017 8:12 PM
>>>>>>> To: Programming at jsoftware.com
>>>>>>> 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
More information about the Programming
mailing list