[Jprogramming] Partitions

Sat Oct 28 12:39:04 UTC 2017

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