[Jprogramming] Partitions

[Erling Hellenäs]

Hi all !

New parRuskey version. Still recursive, but all in once :)

    x=:5
    y=:10
    ts'x parRuskey y'
0.199875 3.89459e7
    ts'x parRuskeyE y'
0.0692546 3.8954e7
    ts'x parRuskeyMD y'
0.176556 3.8954e7

parRuskeyE =: 4 : 0
r=. (,: i.y) SE (x-1);y-1
r </."1 i.y
)

SE =: 4 : 0
'k n' =. y
r=. (0,_1{.$x)$0
if. k=n do.
   r=.x
else.
   s=.n {."1 x
   e=.(n+1)}."1 x
   a=.,/s ( [,"1 1 (i.k+1),"0 1 ])"1 e
   r=.r, a SE k;n-1
   if. k > 0 do.
     a=.s,.k,.e
     r=.r, a SE (k-1);n-1
   end.
end.
r
)

Cheers,

Erling Hellenäs


Den 2017-11-01 kl. 12:13, skrev Erling Hellenäs:
> Hi all!
>
> parRuskey comparison.
>
> Mike Days new version is slightly faster than the Frank Ruskey version.
>
> Cheers,
>
> Erling Hellenäs
>
> ----------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
> v5=. /:~  v4
> (/: #&.> v5){ v5
> )
>
> compare=: -:&:normalize
>
> NB. parELMDE for comparison
>
> parELMDE=: 4 : 0
> a =. ~. i.~"1 iy #: i. */ iy =. (1+i.x),(y-x)$x
> a =. a#~ x = #@~."1 a
> sort a </."1 i. y
> )
>
> NB. Original Frank Ruskey version.
>
> parRuskey =: 4 : 0
> a=: i. y
> r=: (0,y)$0
> (x-1) S y-1
> r </."1 i.y
> )
>
>
> S =: 4 : 0
> if. x=y do.
>   r=:r,a
> else.
>   for_i. i.x+1 do.
>     a=: i y } a
>     x S y-1
>     a=: y y } a
>   end.
>   if. x > 0 do.
>     a=: x y } a
>     (x-1) S y-1
>     a=: y y } a
>   end.
> end.
> )
>
> NB. Slightly modified by Erling to remove global variables.
>
> parRuskeyE =: 4 : 0
> r=. (i.y) SE (x-1);y-1
> r </."1 i.y
> )
>
> SE =: 4 : 0
> 'k n' =. y
> r=. 0{.,:x
> if. k=n do.
>   r=.,:x
> else.
>   for_i. i.k+1 do.
>     r=.r, (i n } x) SE k;n-1
> end.
>   if. k > 0 do.
>     r=.r, (k n } x) SE (k-1);n-1
>   end.
> end.
> r
> )
>
> NB. Modified by Mike Day
>
> parRuskeyMD =: 4 : 0
> NB. L =: 0$~0, 2 + y   NB. debug/understand array of call parameters
> r=. (i.y) SMD (x-1),y-1
> NB. R =: r             NB. debug/understand output
> r </."1 i.y
> )
>
> SMD =: 4 : 0
> NB. L =: L, y, x       NB. debug/understand array of call parameters
> 'k n' =. y
> a =.x
> r =. 0$~ 0, #a
> if. k = n - 1 do.      NB. replace repeated calls with k = n (on entry)
>   r =. (i.k+1) n }"0 1 (k+1)# ,:a  NB. don't need to use recursion here!
> else.
>      NB. is there a way to avoid recursion here,  too?
>   r =. r, ,/ (SMD&(k,n-1))"1 (i.k+1) n }"0 1 a NB.apply "1 instead of 
> do loop
> end.
> if. k > 0 do.
>   r=.r, (k n } a) SMD (k-1),n-1
> end.
> r
> )
>
> x=:1
> y=:1
> (x parELMDE y) compare x parRuskey y
> (x parELMDE y) compare x parRuskeyE y
> NB.(x parELMDE y) compare x parRuskeyMD y - Error
> x=:1
> y=:2
> (x parELMDE y) compare x parRuskey y
> (x parELMDE y) compare x parRuskeyE y
> (x parELMDE y) compare x parRuskeyMD y
> x=:2
> y=:3
> (x parELMDE y) compare x parRuskey y
> (x parELMDE y) compare x parRuskeyE y
> (x parELMDE y) compare x parRuskeyMD y
> x=:3
> y=:5
> (x parELMDE y) compare x parRuskey y
> (x parELMDE y) compare x parRuskeyE y
> (x parELMDE y) compare x parRuskeyMD y
> x=:3
> y=:6
> (x parELMDE y) compare x parRuskey y
> (x parELMDE y) compare x parRuskeyE y
> (x parELMDE y) compare x parRuskeyMD y
>
> x=:5
> y=:10
> ts'x parRuskey y'
> ts'x parRuskeyE y'
> ts'x parRuskeyMD y'
>
>
> -------Output-------------------
>
>
>    x=:1
>    y=:1
>    (x parELMDE y) compare x parRuskey y
> 1
>    (x parELMDE y) compare x parRuskeyE y
> 1
>    NB.(x parELMDE y) compare x parRuskeyMD y - Error
>    x=:1
>    y=:2
>    (x parELMDE y) compare x parRuskey y
> 1
>    (x parELMDE y) compare x parRuskeyE y
> 1
>    (x parELMDE y) compare x parRuskeyMD y
> 1
>    x=:2
>    y=:3
>    (x parELMDE y) compare x parRuskey y
> 1
>    (x parELMDE y) compare x parRuskeyE y
> 1
>    (x parELMDE y) compare x parRuskeyMD y
> 1
>    x=:3
>    y=:5
>    (x parELMDE y) compare x parRuskey y
> 1
>    (x parELMDE y) compare x parRuskeyE y
> 1
>    (x parELMDE y) compare x parRuskeyMD y
> 1
>    x=:3
>    y=:6
>    (x parELMDE y) compare x parRuskey y
> 1
>    (x parELMDE y) compare x parRuskeyE y
> 1
>    (x parELMDE y) compare x parRuskeyMD y
> 1
>
>    x=:5
>    y=:10
>    ts'x parRuskey y'
> 0.204245 3.89459e7
>    ts'x parRuskeyE y'
> 0.316044 3.8954e7
>    ts'x parRuskeyMD y'
> 0.173341 3.8954e7
>
>
> Cheers,
>
>
> Erling Hellenäs
>
>
> Den 2017-10-31 kl. 20:17, skrev 'Mike Day' via Programming:
>> parRuskeynew =: 4 : 0
>> NB. L =: 0$~0, 2 + y   NB. debug/understand array of call parameters
>> r=. (i.y) Snew (x-1),y-1
>> NB. R =: r             NB. debug/understand output
>> r </."1 i.y
>> )
>>
>> Snew =: 4 : 0
>> NB. L =: L, y, x       NB. debug/understand array of call parameters
>> 'k n' =. y
>> a =.x
>> r =. 0$~ 0, #a
>> if. k = n - 1 do.      NB. replace repeated calls with k = n (on entry)
>>   r =. (i.k+1) n }"0 1 (k+1)# ,:a  NB. don't need to use recursion here!
>> else.
>>      NB. is there a way to avoid recursion here,  too?
>>   r =. r, ,/ (Snew&(k,n-1))"1 (i.k+1) n }"0 1 a NB.apply "1 instead 
>> of do loop
>> end.
>> if. k > 0 do.
>>   r=.r, (k n } a) Snew (k-1),n-1
>> end.
>> r
>> )
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm