How to partition arrays

I had this idea in the shower today, and it works.

Let's say you have a big hash of key/value pairs, where the values are numbers and the keys are whatever. You want to divide them evenly into four or five smaller hashes with roughly equal sums of values.

My idea was to first divide them arbitrarily, then do 1000 iterations of moving a random element from the largest to the smallest piece.

And it works! Here's the (Ruby) code:

require "rubygems"
require "activesupport"

def partition values, count, tries = 1000
total = lambda{|s| s.values.sum }

largest = lambda{|s| s.max{|a,b| total[a] <=> total[b]} }

smallest = lambda{|s| s.min{|a,b| total[a] <=> total[b]} }

shift = lambda{|from, to|
key = from.keys.rand
to[key] = from.delete(key)
}

partitions = []
count.times{ partitions << {} }
values.keys.each_with_index{|key,i| partitions[i%count][key] = values[key] }

tries.times{ shift[ largest[partitions], smallest[partitions] ] }

partitions
end

Use it like this:

values = {}
(1..100).each{|n| values[n] = n }
partition(values, 5)

It'll yield 5 hashes, the sums of the values of each of which are 1010. Neat, huh?