OpenEuphoria

Re: Murphy still winning

• Posted by "C. K. Lester" <cklester at yahoo.com> May 14, 2003
• 397 views

Can you make this so that the number of groups is variable? For instance,
sometimes I need to put those values across 3 or 4 or more buckets... :)

----- Original Message -----
From: <rforno at tutopia.com>
To: "EUforum" <EUforum at topica.com>
Subject: Murphy still winning


>
> The "omega" version:
>
> --Group numbers into two groups such that their sums are as close as
> possible
> --R. M. Forno 2003/04/17
> include sort.e
> include get.e
> include misc.e
> include machine.e
>
> integer Last, Lendata, Bestlast
> atom Lowgoal, Highgoal, Val, Bestval, Totval, Limit, Bound
> sequence Data, Index, Accum, Bestind
>
> set_rand(1)
>
> function Mcd2(integer d, integer r)
>     integer x
>     while r do
>     x = remainder(d, r)
>     d = r
>     r = x
>     end while
>     return d
> end function
>
> function Mcd(sequence s)
>     integer len, r
>     len = length(s)
>     r = s[len]
>     for i = len - 1 to 1 by -1 do
>     if r = 1 then
>         return r
>     end if
>     r = Mcd2(r, s[i])
>     end for
>     return r
> end function
>
> 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 >= Bound then
>         if Val > Bestval then --Test for better value
>         Bestval = Val --Update best value and corresponding indexes
>         Bestlast = Last
>         Bestind = Index
>         end if
>     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]
>     Bound = Lowgoal - Data[1]
>     Bestind = Index
>     r = recurse()
>     if Bestval = 0 then
>     Bestval = Data[1]
>     end if
> end procedure
>
> function genrand(integer n, integer m)
>     sequence s
>     s = 14 * rand(repeat(n, m))
>     s[1] += 1
>     s[length(s)] += 1
>     return s
> end function
>
> procedure main()
>     atom t
>     integer a, b, mcd, r
>     a = 10000
>     b = 28
> --  Data = readseq()
>     Data = genrand(a, b)
> --  Data = {111, 9, 9, 9, 9, 9, 5, 1, 1, 1}
>     t = time()
>     Lendata = length(Data)
>     Index = repeat(0, Lendata)
>     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)
>     mcd = Mcd(Data)
>     Lowgoal -= remainder(Lowgoal, mcd)
>     r = remainder(Highgoal, mcd)
>     if r then
>         Highgoal += mcd - r
>     end if
>     if Totval - Highgoal < Lowgoal then
>         Lowgoal = Totval - Highgoal
>     end if
>     if Totval - Lowgoal > Highgoal then
>         Highgoal = Totval - Lowgoal
>     end if
>     printf(2, "Lowgoal = %d, Highgoal = %d\n", {Lowgoal, Highgoal})
>     optim()
>     end if
>     printf(2, "n = %d m = %d Sum1 = %d Sum2 = %d Time: %f\n",
>         {a, b, Bestval, Totval - Bestval, time() - t})
>     outputresult()
> end procedure
>
> main()
>
>
>
> TOPICA - Start your own email discussion group. FREE!
>
<snip>