Hallo Skip Cave, je schreef op 16-04-11 18:21:
> On 4/15/2011 3:32 PM, R.E. Boss wrote:
>> [bm=: nb %~ +/ m
>> 51.5
>>
>> ]'a b'=.(,~nb&-) nb * (-<.) x: bm
>> 1 1
>>
> Hmmm. You are right. This is not the way to find the set of nb integers
> that sum to #m and have a minimal difference.
>
> Skip
It only means that this ideal set of bucket sums can not be realized (as in a
lot of other cases).
As I mentioned already
> I'm not sure of course if this particular partitioning (a,b) of integer bucket
> sums is possible.
The example R.E. Boss presented as an impossible ideal goal doesn't influence
my
quoted doubt in this. Even with the (nice) low scale example you're not sure if
the ideal bucket sum partitioning can be obtained. Intuitively (o my!) I can
only say that in the latter case 'the chance for obtaining the ideal set of
bucket sums is more plausible'.
Anyway: the ideal set
(a,b) # (,>:) <. 4%~+/m
could serve as a measure to compare with a generated sample of bucket contents
as follows:
G=. ds +/&> (a,b) # p1,p2
* ds : see below
Use G to compare with a generated p0;p1;,,,,;pk
----------- Just for a start -----------------------------
Split the solution method into two phases (as Victor suggested).
Assume you have a simple and fast partitioning of weights phase I (I'll show a
not so smart one hereafter) with a very good result p, then phase II could be
an
optimizing algorithm as follows:
NB. total difference sum of bucket sums
ds=: [: +/ [: ; <@({. |@- }.)\.
NB. kind of cross mutation on a pair of different buckets
NB. just swapping 1 element each on the 'low' side of the sorted (/:~) bucket
contents
mutate=: 4 :0
'a b'=. y
i=.?x<.#a
j=.?x<.#b
((j{b) i} a);(i{a) j}b
)
phaseII=: 4 :0
ne=.100 NB. # elements
ng=.50 NB. # generations
mr=.2 NB mutation argument
b=. /:~&.> y
ws=. ne $ <b
z=.i.0 0
for. i.ng do.
p=.i.0 0
for_e. ws do.
d=.>e
en=. mr mutate d{~ ix=.2?x
p=.p, en (ix) } d
end.
z=. z,m=. p {~(i. <./) ds@:(+/&>)"1 p=.p,b
ws=. ne $< /:~&.> m
end.
z {~(i.<./) ds@:(+/&>)"1 z
)
* experiment with ne, ng and mr
Using low scale ex. m
In the following 'distrib' is a specialized verb only usable for the low scale
example m. It regularly produces the ideal set.
+/&> p=.distrib''
123 122 123 125
+/&> 4 phaseII ,p
123 124 123 123
Ideal set of bucket sums (as shown in prev. e-mail)
1 3 # 124 123
124 123 123 123
goal to achieve:
ds 1 3 # 124 123
3
Like obtained by phaseII
ds 123 124 123 123
3
----------------------------------------
A very simple but not smart phaseI verb
PHI=: 4 :0
'a b'=.x
ns=.1000
z=.([:<"1 x&$)"1 ns(([: , (,:y) $~ [) {~ (?~@#)) #y
z {~(i. <./) ds@:(+/&>)"1 z
)
Using the large scale example:
M=. ?. 200#1000
10%~+/M
9757.2
Ideal set
((,~10&-)10*(-<.) x: av)#(,>:) <.av=.10%~+/M
9757 9757 9757 9757 9757 9757 9757 9757 9758 9758
Minimum total diff sum (goal to achieve):
ds 9757 9757 9757 9757 9757 9757 9757 9757 9758 9758
16
Sample run with fixed bucket size of 20
ts 'it=.10 phaseII M PHI ~ 10 20'
2.73345 3.1513e6
Unfortunately the total diff. sum is far away from 16
ds +/&>it
6984
Rests the hunt for a fast and simple phaseI that produces an already very good
result. :-)
--
Met vriendelijke groet,
=@@i
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
