1. RE: Algorithm Request
- Posted by Matt Lewis <matthewwalkerlewis at yahoo.com> Apr 07, 2003
- 382 views
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. Are you concerned with the sum of the numbers? Standard deviation? Product? etc... Matt Lewis > From: C. K. Lester [mailto:cklester at yahoo.com] > 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 Matt Lewis <matthewwalkerlewis at yahoo.com> Apr 07, 2003
- 361 views
> From: C. K. Lester [mailto:cklester at yahoo.com] > > 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 Here's what I came up with real quick. There's probably a more elegant solution, but this should work for any number of sets you want to make: include get.e include sort.e function sums(sequence nums) sequence sum integer add sum = repeat(0,length(nums)) for i = 1 to length(nums) do add = 0 for j = 1 to length(nums[i]) do add += nums[i][j] end for sum[i] = add end for return sum end function procedure main() integer mid, ideal, sum, d, rep, max, pick_max, min, pick_min, over, under sequence buckets, bucket_sums, rnd sum = 0 rnd = repeat( 0, 100 ) for i = 1 to length(rnd) do rnd[i] = rand(1000) sum += rnd[i] end for rnd = sort(rnd) puts(1,"Numbers:\n") ? rnd puts(1,"\n") for b = 2 to 5 do ideal = floor(sum/b) buckets = repeat({},b) max = 1 while max <= length(rnd) do for i = 1 to b do if max > length(rnd) then exit end if buckets[i] &= rnd[max] max += 1 end for end while bucket_sums = sums(buckets) rep = 0 d = sum while d and (rep < 100) do max = 0 pick_max = 0 min = sum for i = 1 to b do if bucket_sums[i] > max then max = bucket_sums[i] pick_max = i end if if bucket_sums[i] < min then min = bucket_sums[i] pick_min = i end if end for -- remove one number from pick_max and give to pick_min over = bucket_sums[pick_max] - ideal under = ideal - bucket_sums[pick_min] -- choose which number to give away for i = length(buckets[pick_max]) to 1 by -1 do if buckets[pick_max][i] < over + under then buckets[pick_min] = sort( buckets[pick_min] & buckets[pick_max][i] ) buckets[pick_max] = buckets[pick_max][1..i-1] & buckets[pick_max][i+1..length(buckets[pick_max])] exit end if end for bucket_sums = sums( buckets ) d = 0 min = 0 for i = 1 to length(bucket_sums) do max = bucket_sums[i] - ideal if max < 0 then max = -max end if if max > min then min = max d = min end if end for rep += 1 end while printf(1,"\nbuckets: %d ideal: %d max: %d reps: %d\n", {b,ideal,d, rep} ) ? bucket_sums for i = 1 to b do ? buckets[i] end for end for end procedure main() if wait_key() then end if
3. RE: Algorithm Request
- Posted by rforno at tutopia.com Apr 11, 2003
- 378 views
Pete and all: I really liked the problem posed by C. K. Lester, and developed my own code. I am thinking in using it as a challenge for my students of C/C++ and Java, to excite competition (a prize for the fastest lgorithm). Following is my solution, which in many cases takes nearly no time having as input huge sequences, such as the one in the example (10000 random numbers between 1 and 10000). It is really strange for a backtracking algorithm, having several shortcuts. Regards. This is the code: --Group numbers into two groups such that their sums are as close as possible --R. M. Forno 2003/04/10 include sort.e include get.e include misc.e include machine.e integer Last, Lendata, Bestlast atom Lowgoal, Highgoal, Val, Bestval, Totval, Limit sequence Data, Index, Accum, Bestind set_rand(1) function readseq() --Read a sequence of integers from the keyboard or from a redirected file sequence s, r s = {} while 1 do r = get(0) if r[1] != GET_SUCCESS or not integer(r[2]) then exit end if s &= r[2] end while return s end function procedure outputresult() --Output resulting partitions sequence aux aux = repeat(0, Lendata) for i = 1 to Lendata do aux[i] = i end for for i = 1 to Bestlast do aux[Bestind[i]] = 0 end for printf(1, "Best solution values: %d %d\n", {Bestval, Totval - Bestval}) puts(1, "Partition 1:\n") for i = 1 to Bestlast do printf(1, "%d ", Data[Bestind[i]]) end for puts(1, '\n') puts(1, "Partition 2:\n") for i = 1 to Lendata do if aux[i] then printf(1, "%d ", Data[aux[i]]) end if end for puts(1, '\n') end procedure function recurse() integer ind, r, dat, i1 if Val > Highgoal then --Impossible to get better values return 0 elsif Val < Lowgoal then --Try to go ahead if Val > Bestval then --Test for better value Bestval = Val --Update best value and corresponding indexes Bestlast = Last Bestind = Index end if if Val > Limit then --Impossible to get better values return 0 end if ind = Index[Last] --Go to next data item while 1 do i1 = ind --Previous ind += 1 if ind > Lendata then --End of data vector return 0 end if if Val + Accum[ind] <= Bestval then --Impossible to get better value return 0 end if dat = Data[ind] if dat != Data[i1] or Index[Last] = i1 then --Skip repetition Last += 1 --Try next index Index[Last] = ind Val += dat r = recurse() if r then --Best possible value found return 1 end if Val -= dat --Restore previous value Last -= 1 end if end while else Bestval = Val --Either Val = Lowgoal or Val = Highgoal Bestlast = Last Bestind = Index return 1 --Indicate best possible value found end if end function procedure optim() integer r Bestval = 0 Last = 1 Bestlast = 1 Index[1] = 1 Val = Data[1] Limit = Highgoal - Data[Lendata] Bestind = Index r = recurse() end procedure function genrand(integer n, integer m) sequence s s = rand(repeat(n, m)) return s end function procedure main() atom t integer a, b a = 10000 b = 10000 -- Data = readseq() Data = genrand(a, b) Lendata = length(Data) Index = repeat(0, Lendata) t = time() if Lendata = 0 then Bestlast = 0 Totval = 0 Bestval = 0 elsif Lendata = 1 then Bestlast = 1 Bestind = {1} Totval = Data[1] Bestval = Totval else Data = reverse(sort(Data)) Accum = Data for i = Lendata to 2 by -1 do Accum[i - 1] += Accum[i] end for Totval = Accum[1] Lowgoal = floor(Totval * 0.5) Highgoal = - floor(- Totval * 0.5) optim() end if printf(2, "n = %d m = %d Time: %f\n", {a, b, time() - t}) outputresult() end procedure main() ----- Original Message ----- From: Pete Lomax <petelomax at blueyonder.co.uk> To: EUforum <EUforum at topica.com> Sent: Monday, April 07, 2003 9:51 PM Subject: 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={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=1 to dlevel do ib=dset[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=1 lowbest=0 highbest=999999999 item=length(sizes) includeset=repeat(0,item) worktot=0 while 1 do includeset[level]=item worktot+=sizes[item] if worktot=required then -- Found exact fit lowbest=worktot lowlevel=level lowset=includeset return end if if worktot<required and worktot > lowbest then lowbest=worktot lowlevel=level lowset=includeset end if if item > 1 -- More to be tested and worktot<required then item-=1 level+=1 -- Leave item in table; else if worktot>required and worktot < highbest then highbest=worktot highlevel=level highset=includeset end if while 1 do -- -- Now we need to backtrack; remove item from running -- total and look at the next instead. -- worktot-=sizes[item] if item > 1 then -- More to be tested item-=1 -- Look at next (overwrite item in table) exit end if -- -- We have exhausted all possibilities at this level; -- backtrack to a previous level. -- includeset[level]=0 level-=1 if level=0 then return end if -- All done item=includeset[level] end while end if end while end procedure procedure main() required=0 for i=1 to length(sizes) do required+=sizes[i] end for required=floor(required/2) printf(1,"Required: %d\n",{required}) sizes=sort(sizes) find_combination() if lowbest=required 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() ==^^=============================================================== This email was sent to: rforno at tutopia.com TOPICA - Start your own email discussion group. FREE!