1. Algorithm Request
Is there an algorithm out there that will take a series of numbers and put
them in groups of equal amounts? For instance, I have these numbers:
377
378
384
387
388
391
396
422
424
425
488
505
I need them placed in two groups, as close to being equal in value as
possible.
I'm sure there's something out there... if not, I challenge everyone to a
EUPHORIA programming contest! :)
2. Re: Algorithm Request
Howdy, Matt,
When I said, "as close to being equal in value as possible," I meant their
sums...
> Could you define 'equal amounts?' I assume you don't mean simply
splitting
> n numbers into k piles, so that each pile k has either int(n/k) or
> int(n/k)+1 numbers.
Right. I don't mean that...
> Are you concerned with the sum of the numbers?
Yes!
So, with this set:
1, 2, 4, 5, 8, 11
split into two groups, it would create TWO groups of 3 numbers each whose
sums were the closest possible to equal...
1, 4, 11 = 16
2, 5, 8 = 15
When there are groupings of equal difference, uh... I don't know. Doesn't
matter at this point...
Thanks!
3. Re: Algorithm Request
I did this manually, just to check myself. This is what I got:
A = {377,378,391,424,425,488}
B = {384,387,388,396,422,505}
sumA = 2483
sumB = 2482
Method:
There could easily be multiple answers to this problem, so I assume
that any best answer will do.
1. Sort the list of numbers into ascending order
2. Take the bottom 25% and the top 25% and place them in column A.
3. Take the remaining center 50% and place them in column B.
4. SwapFactor = floor(abs(sumA - sumB)/2)
5. For each index x in A and index y in B, find the pair (x,y) so that
abs(A[x]-B[y]) is closer to SwapFactor than any other pair. If sumA >
sumB then A[x] > B[y] else A[x] < B[y].
6. Swap A[x] with B[y] and recalc sumA and sumB remembering A[x] and
B[y] in case we need to unswap.
7. SwapFactor2 = floor(abs(sumA-sumB)/2)
8. if SwapFactor2 > SwapFactor then unswap and stop, else repeat steps
4 through 8.
I don't have time right now to code this and test it, and I'm sure
someone else will find a much faster method in a few minutes anyway.
HTH,
Michael J. Sabal
>>> cklester at yahoo.com 04/07/03 03:37PM >>>
Is there an algorithm out there that will take a series of numbers and
put
them in groups of equal amounts? For instance, I have these numbers:
377
378
384
387
388
391
396
422
424
425
488
505
I need them placed in two groups, as close to being equal in value as
possible.
I'm sure there's something out there... if not, I challenge everyone to
a
EUPHORIA programming contest! :)
TOPICA - Start your own email discussion group. FREE!
4. Re: Algorithm Request
> I don't have time right now to code this and test it, and I'm sure
> someone else will find a much faster method in a few minutes anyway.
I think most solutions coming in are of the "what's the difference, find the
pair to swap that will make the difference less..."
Now, let's see some code, people!
5. Re: Algorithm Request
On Mon, 7 Apr 2003 16:01:45 -0500, "C. K. Lester" <cklester at yahoo.com>
wrote:
Over ten years ago I wrote a best fit algorithm in COBOL, no less,
without recursion (and plenty of goto statements). I've wanted to
recode it in Euphoria for ages, and now I have.
--
-- Optimised best-fit algorithm
-- Pete Lomax 7th April 2003
--
include sort.e
integer required
sequence sizes
sizes=3D{377,378,384,387,388,391,396,422,424,425,488,505}
sequence includeset
integer lowbest, lowlevel, highbest, highlevel, worktot, level, item
sequence lowset, highset
procedure display(sequence dtext, integer dtot, sequence dset, integer
dlevel)
integer ib
printf(1,"%s %d\n",{dtext,dtot})
for b=3D1 to dlevel do
ib=3Ddset[b]
printf(1,"%d %d\n",{ib,sizes[ib]})
end for
if getc(0) then end if
end procedure
procedure find_combination()
--
-- This section tries to find a set of sizes which add up to the
-- required amount exactly.
--
level=3D1
lowbest=3D0
highbest=3D999999999
item=3Dlength(sizes)
includeset=3Drepeat(0,item)
worktot=3D0
while 1 do
includeset[level]=3Ditem
worktot+=3Dsizes[item]
if worktot=3Drequired then -- Found exact fit
lowbest=3Dworktot
lowlevel=3Dlevel
lowset=3Dincludeset
return
end if
if worktot<required and worktot > lowbest then
lowbest=3Dworktot
lowlevel=3Dlevel
lowset=3Dincludeset
end if
if item > 1 -- More to be tested
and worktot<required then
item-=3D1
level+=3D1 -- Leave item in table;
else
if worktot>required and worktot < highbest then
highbest=3Dworktot
highlevel=3Dlevel
highset=3Dincludeset
end if
while 1 do
--
-- Now we need to backtrack; remove item from running
-- total and look at the next instead.
--
worktot-=3Dsizes[item]
if item > 1 then -- More to be tested
item-=3D1 -- Look at next (overwrite item in table)
exit
end if
--
-- We have exhausted all possibilities at this level;=20
-- backtrack to a previous level.
--
includeset[level]=3D0
level-=3D1
if level=3D0 then return end if -- All done
item=3Dincludeset[level]
end while
end if
end while
end procedure
procedure main()
required=3D0
for i=3D1 to length(sizes) do
required+=3Dsizes[i]
end for
required=3Dfloor(required/2)
printf(1,"Required: %d\n",{required})
sizes=3Dsort(sizes)
find_combination()
if lowbest=3Drequired then
display("Exact fit",lowbest,lowset,lowlevel)
else
display("Lower figure",lowbest,lowset,lowlevel)
display("Higher figure",highbest,highset,highlevel)
end if
end procedure
main()
