Balancing sets of values

Question

So I'm working on a fun little program and ran across this rather interesting problem: I have several sets of values of pre-defined set sizes. These are all a unique subset of a larger pool of values. The averages of each subset of numbers should be as close to each other as reasonably possible. This does not need to be perfect, but should be close enough that all sets are "balanced" against each other.

ex: {1,2,3,6,9,10,15,23,27} global mean: 10.66 needs to be sorted into 2 sets of 2 and one set of 5

acceptable result: {1,27}{2,23}{3,6,9,10}

In practice, the values will range between 60 and 200, and the sets will range from size 6 to 20.

I've tried a couple different algorithms, with various degrees of success, but I was interested in seeing what the good people at StackOverflow think.

My best, Zach

Answer 1

This sounds interesting. would love to know whats the practical application of this.

Just to be sure, guess you meant non intersecting subsets and sum of subsets be roughly equal (and not the averages)

Also, in the example I couldn't understand how you decided (for sure) to make 2 sets of 2 and one of 5.

I can think of a greedy sub optimal solution.

1. Sort the numbers decreasing order order. (smaller numbers surprise less so deal them later)
2. Decide on the number of sets you are going to have. not too sure about this
3. Go through the set elements one by one and put them into the subset which has the lowest sum (round robin in case of equal sums)

This will not always give you the optimal solution though.

For 1,2,3,6,9,10,15,23,27 reversed: 27, 23, 15, 10, 09, 06, 03, 02, 01

27 3 2 1 = 33

23 09 = 30

15 10 06 = 31

Answer 2

This reminds me of RubyQuiz #65, "Splitting the Loot". The major difference is that that problem was looking for splits that were exactly equal, instead of nearly equal. Maybe some of those solutions will help you.