Here's the reasonably constructive approach.
Much better than my earlier effort at a constructive approach,
but it still generates too much redundancy as x approaches y
for larger y. Limited time to do email, so in a bit of a rush...
NB. Generate non-zero partitions of y size x
3 mpart 5 NB. eg
2 2 1
3 1 1
mpart =: 3 : 0
:
m =. x [ n =. y
NB. smoutput m;n
if. m = 1 do. ,: n return. end.
max =. n + 1 - m
min =. >.n%m
l =. ,.min ([+i.@>:@-~ ) max
for_j. >:}:}. i.m do.
rem =. n - +/"1 l
min =. >. rem%(m + 1 - j)
max =. min >. ({:"1 l) <. rem - m - j
nl =. 0-.~, min ([+i.@>:@-~ )"0 max
l =. nl,.~ l#~1 + max - min
end.
l,. n - +/"1 l
)
NB. CONSTruct boxed outputs for a given arrangement of partition sizes
NB. eg const 2 4 3 as a contribution to 3 par 9
require'stats' NB. for comb
const =: 3 : 0
p =. y NB. eg 2 4 3
n =. +/p
r =. comb/({.,+/)p NB. initialise with first group-size
last =. done =. {.p
in =. i.n
s =. 0
for_pi. }:}.p do. NB. add on intermediate groups - last is
implicit
ri =. comb/ pi,n - done
ini =. r -. "1~ in NB. commute is silly, no time to change it!
r =. r#~#ri
add =. ,/ ri&{"1 ini
if. last = pi do. NB. only need to check for redundancy
NB. when repeating partial group size
ok =. (s{"1 r) < {."1 add
r =. ok#r
add=. ok#add
end.
r =. r,. add
done =. done + pi
s =. s + last
last =. pi
end.
NB. append last group-size sub-array
if. last = {:p do. NB. check redundancy if same group-size as
previous
ok =. (s{"1 r) < {."1 add =. r -."1 ~ in
r =. (ok#r),. ok#add
else.
r =. r,. r -."1 ~ in
end.
(p#i.#p) </."1 r
)
NB. constructive verb for (eg) 3 par 9
NB. Fairly efficient cf Raul's, but still suffers from
NB. big-O problems
mdconst =: 3 : 0
mdconst/y
:
NB. special cases, pace Erland!
if. x >: y do. r =. <"0 i.(x=y){0 0,:1,x
elseif. x = 1 do. r =. 1 1$<i.y
elseif. 1 do.
p =. x mpart y
r =. const {.p
for_pi. }.p do.
r =. r, const pi
end.
end.
)
|: mdconst 3 4
+---+---+---+---+---+---+
|0 1|0 2|0 3|1 2|1 3|2 3|
+---+---+---+---+---+---+
|2 |1 |1 |0 |0 |0 |
+---+---+---+---+---+---+
|3 |3 |2 |3 |2 |1 |
+---+---+---+---+---+---+
ts'mdconst 3 9'
0.0177876 1.37434e6
ts'parRDM/ 3 9'
0.0179469 995968
ts'mdconst 5 9'
0.0728827 5.22534e6
ts'parRDM/ 5 9'
0.0815166 4.38822e6
ts'mdconst 8 9'
0.00567922 543360
ts'parRDM/ 8 9'
0.00107666 61952
Must go now!
Mike
>----Original Message----
>From: [email protected]
>Date: 30/10/2017 14:17
>To: <[email protected]>
>Subj: Re: [Jprogramming] Partitions
>
>Yes - even with your improvement, it works by filtering an ever
larger array. I’ll post separately a reasonably “constructive”
approach, which is closer to Raul’s method in performance, I think.
>Mike
>
>Please reply to [email protected].
>Sent from my iPad
>
>> On 29 Oct 2017, at 19:37, Erling Hellenäs <[email protected]>
wrote:
>>
>> Hi all!
>>
>> I took a sample. We must remember that when we have 10 buckets and
10 elements, we get only one combination.
>> However, it seems Rauls algorithm is better for high y. parELMDE
still generates too many unused combinations.
>>
>> x=:5
>> y=:10
>> ts'x parR y'
>> 0.211737 2.7077e7
>> ts'x parELMDE y'
>> 0.417241 1.1325e8
>> ts'x parMD y'
>> 2.30795 1.71128e9
>>
>> Cheers,
>>
>> Erling Hellenäs
>>
>>> On 2017-10-29 17:53, Raul Miller wrote:
>>> Ah, excellent.
>>>
>>> require'stats'
>>>
>>> parRDM=: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
>>> )
>>>
>>> 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
>>> )
>>>
>>> timerat=:4 :0"0
>>> try.
>>> elmde=.6!:2 'vE=. x parELMDE y'
>>> rdm=.6!:2 'vR=. x par y'
>>> r=. rdm%elmde
>>> catch.
>>> vR=.vE=.0
>>> r=. _
>>> end.
>>> assert. vR -:&(/:~)&:(/:~"1)&:(/:~&.>) vE
>>> r
>>> )
>>>
>>> For the simple (and fast) cases, parELMDE tends to be significantly
>>> faster than my parRDM. Low complexity pays off:
>>>
>>> 3 timerat 4
>>> 2.59375
>>>
>>> However, for other cases, it tends to be significantly slower.
Here,
>>> low complexity does not pay off enough to amortize big-O issues:
>>>
>>> 6 timerat 8
>>> 0.067733
>>>
>>> Or, a slightly better overview (better viewed with fixed width font
or
>>> run it yourself):
>>>
>>> 9!:11]3 NB. reduce display precision, for email line widths
>>>
>>> (1+i.10) timerat table 1+i.10
>>>
┌───────┬─────────────────────────────────────────────────────────────┐
>>> │timerat│ 1 2 3 4 5 6 7 8 9
10│
>>>
├───────┼─────────────────────────────────────────────────────────────┤
>>> │ 1 │1.03 1.38 1.67 1.82 2.3 2.5 2.9 3.1 3.4
3.7│
>>> │ 2 │ _ 5.43 3.28 5.13 3.6 3.95 2.36 2.37 1.52
1.58│
>>> │ 3 │ _ _ 5.46 3.24 3.24 2.27 1.46 1.43 0.83
0.763│
>>> │ 4 │ _ _ _ 2.94 1.74 1.44 0.961 0.668 0.599
0.621│
>>> │ 5 │ _ _ _ _ 2.08 0.514 0.374 0.325 0.315
0.311│
>>> │ 6 │ _ _ _ _ _ 0.566 0.0929 0.0876 0.0951
0.124│
>>> │ 7 │ _ _ _ _ _ _ 0.0936 0.0156 0.0177
0.0323│
>>> │ 8 │ _ _ _ _ _ _ _ 0.0117 0.00192
0.00209│
>>> │ 9 │ _ _ _ _ _ _ _ _ 0.00256
0.000176│
>>> │10 │ _ _ _ _ _ _ _ _ _
0.00019│
>>>
└───────┴─────────────────────────────────────────────────────────────┘
>>>
>>> Thanks,
>>>
>>
>>
----------------------------------------------------------------------
>> 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
