Hi all!
Here Mike Days modification of Esa Lippu algorithm with a fix to
generate less combinations.
Faster and uses less memory.
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
)
ts'x parELMDE y'
0.000135765 61440
ts'x parMD y'
0.000311426 224640
Cheers,
Erling Hellenäs
On 2017-10-29 02:16, Raul Miller wrote:
Here's a debugged version of par that seems to have reasonable
performance (and good big-O structure):
require'stats'
par=:4 :0
x (1+y-x) P y
)
combine=:1 :0
:
q=.(#;{.x)=#@>y
if.1 e.,q do.
b=. ,(<./@>x)<:/ q <./@;@#"1 y
b # ,/ x ([,] ({L:0 ,) (i.m)-.S:0 [)"0 1/ y
else.
,/ x ([,] ({L:0 ,) (i.m)-.S:0 [)"0 1/ y
end.
)
P=:1 :0
:
NB. x: number of partitions
NB. m: maximum allowed partition size
NB. y: number of items to distribute across partitions
if. y>x*m do.return. end.
if. (0=m)+.y<x do.return.end.
if.1=x do. ,.<"1 m comb y return.end.
r=.i.0 0
for_n. 1+i.m do.
t=.(x-1) (m<.(y-n)<.n) P y-n
if. 0=#t do. continue. end.
c=.<"1 n comb y
r=.r, c y combine t
end.r
)
This could obviously be made a bit more concise,
I haven't really been tracking this thread to figure out which are the
good performing (and, working properly) variants to test against, if
performance is an issue. I have, however, tested it a bit for
correctness. Here's the "test suite":
NB. borrowed from Lippu Esa
nparts=: 4 : 0
a=.(y#x) #: i. x^y
sort ~.((x=#@~."1 a)#a) </."1 i.y
)
chk=:2 :0
:
try.
assert x (u -:&(/:~)&:(/:~"1)&:(/:~&.>) v) y
catch.
echo (":x),' par ',(":y),' NB. failed'
throw.
end.
)
check=:par chk nparts
1 check 1
1 check 2
2 check 2
1 check 3
2 check 3
3 check 3
1 check 4
2 check 4
3 check 4
4 check 4
1 check 5
2 check 5
3 check 5
4 check 5
5 check 5
1 check 6
2 check 6
3 check 6
4 check 6
5 check 6
6 check 6
Thanks,
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
