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,
--
Raul
On Thu, Oct 26, 2017 at 12:18 PM, Raul Miller <[email protected]> wrote:
> Oh, yes, it's buggy also :/
>
> Sorry, I'm not really focusing on this problem very much...
>
> Thanks,
>
> --
> Raul
>
> On Thu, Oct 26, 2017 at 11:59 AM, 'Skip Cave' via Programming
> <[email protected]> wrote:
>> Raul,
>>
>> In your new proposed explicit par, for my problem, m=. y-x-1.
>>
>> This is assuming every partition must have at least one item.
>>
>> Skip
>>
>>
>> Skip Cave
>> Cave Consulting LLC
>>
>> <<<>>>
>>
>> On Thu, Oct 26, 2017 at 10:39 AM, Raul Miller <[email protected]> wrote:
>>
>>> Yes...
>>>
>>> Here's my current working draft - I really want to replace that ~./:"1
>>> phrase with something more analytic, but I just think too slowly:
>>>
>>> require'stats'
>>>
>>> par=:4 :0
>>> x (1+y-x) P y
>>> )
>>>
>>> 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.i.0 0 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<.x-1) P y-n
>>> c=.<"1 n comb y
>>> r=.r, ~. /:~"1 ,/c ([,] ({L:0 ,) (i.y)-.S:0 [)"0 1/ t
>>> end.
>>> )
>>>
>>> Basically, I need to be doing something just a bit different when
>>> dealing with a sequence of equal sized partitions.
>>>
>>> Any suggestions?
>>>
>>> Thanks,
>>>
>>> --
>>> Raul
>>>
>>>
>>>
>>>
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
