OpenEuphoria

RE: Algorithm Request

• Posted by Matt Lewis <matthewwalkerlewis at yahoo.com> Apr 07, 2003
• 448 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