title: Spread objects evenly over multiple collections
body: <p>The scenario is that there are <code>n</code> objects, of different sizes, unevenly spread over <code>m</code> buckets. The size of a bucket is the sum of all of the object sizes that it contains. It now happens that the sizes of the buckets are varying wildly.</p>
  
  <p>What would be a good algorithm if I want to spread those objects evenly over those buckets so that the total size of each bucket would be about the same? It would be nice if the algorithm leaned towards less move size over a perfectly even spread.</p>
  
  <p>I have this naïve, ineffective, and buggy solution in Ruby.</p>
  
  <pre class="lang-rb prettyprint-override"><code>buckets = [ [10, 4, 3, 3, 2, 1], [5, 5, 3, 2, 1], [3, 1, 1], [2] ]
  
  avg_size = buckets.flatten.reduce(:+) / buckets.count + 1
  
  large_buckets = buckets.take_while {|arr| arr.reduce(:+) &gt;= avg_size}.to_a
  
  large_buckets.each do |large|
    smallest = buckets.last
  
    until ((small_sum = smallest.reduce(:+)) &gt;= avg_size)
      break if small_sum + large.last &gt;= avg_size
      smallest &lt;&lt; large.pop
    end
  
    buckets.insert(0, buckets.pop)
  end
  
  =&gt; [[3, 1, 1, 1, 2, 3], [2, 1, 2, 3, 3], [10, 4], [5, 5]]
  </code></pre>