class PoolBalancing

Public Class Methods

balance(values, nbpools) click to toggle source
# File lib/pool_balancing.rb, line 2
def self.balance(values, nbpools)
        values.sort! { |a,b| b[0] <=> a[0] }
        pools = Array.new( nbpools ) { Array.new }
        poolsum = Array.new( nbpools, 0 )
        out = Array.new

        ind = 0; dir = 1
        values.each do |val|
                pools[ind] << val
                poolsum[ind] += val[0]
                ind += dir;
                if( ind == nbpools ) then ind = nbpools-1; dir = -1; end
                if( ind == -1 ) then ind = 0; dir = 1; end
        end

        while out.length < (nbpools-1)
                minmax = poolsum.each_with_index.minmax.map{ |t| t[1] }
                diff = poolsum[minmax[1]] - poolsum[minmax[0]]
                return pools.map { |p| p.map { |v| v[1]  }  } if diff <= 1 && out.empty?

                ind = 0
                delete = true
                while ind < pools[minmax[1]].length && delete == true
                        maxval = pools[minmax[1]][ind][0]
                        minval = pools[minmax[0]][ind][0]

                        if (poolsum[minmax[1]] - 2 * maxval + 2 * minval - poolsum[minmax[0]]).abs < diff
                                pools[minmax[1]][ind][0] = minval
                                pools[minmax[0]][ind][0] = maxval
                                poolsum[minmax[1]] += (minval - maxval)
                                poolsum[minmax[0]] += (maxval - minval)
                                delete = false
                                pools.concat(out.pop) && out.clear unless out.empty?
                        end
                        ind+=1
                end

                out << pools.delete_at(minmax[0]) if delete
        end
end