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