OpenEuphoria

RE: Algorithm Request

• Posted by rforno at tutopia.com Apr 11, 2003
• 377 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!