1. RE: Algorithm Request
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
> 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
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!
