1. Algorithm Request
- Posted by "C. K. Lester" <cklester at yahoo.com> Apr 07, 2003
- 378 views
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
- Posted by "C. K. Lester" <cklester at yahoo.com> Apr 07, 2003
- 390 views
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
- Posted by Sabal.Mike at notations.com Apr 07, 2003
- 373 views
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
- Posted by "C. K. Lester" <cklester at yahoo.com> Apr 07, 2003
- 370 views
> 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
- Posted by Pete Lomax <petelomax at blueyonder.co.uk> Apr 08, 2003
- 370 views
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()