Theory question

[Chavo]

I hate doing things the hard way, but in this case I have not been able to think of an alternative yet.

-I have a finite, positive number of integers (in most cases between 3 and 20)
-I want to split the integers into two groups such that their sums are as equal as possible (easy)
-One group must not have a size greater than the other group + 1 (they must be of equal size when there is an even number of elements and as close as possible in size when there is an odd number of elements)

now the part that I'm having trouble with:

-I want to find the top X combinations of groupings with the closest total sums (not just the top 1)

Obviously, I need calculate the sums for every possible combination, but I'm having trouble figuring out an efficient way to do this. Any ideas on a strategy to approach this or a recommended data structure?

My initial thought was an ordered binary tree, but now I think that would just make it more difficult than it needs to be.

[MyndFyre]

A B-tree would be the most convenient way of doing this to get the first 2 (at most) combinations of groupings.

It occurs to me that an ordered binary tree might work as well.  Consider the layout:


[This is theory on my part]

The way to generate a close pair of sums would be to alternate addition, like so:
1 -> Set 1
2 -> Set 2
3 -> Set 2
4 -> Set 1
5 -> Set 1
6 -> Set 2
8 -> Set 2

Because this is an odd number, this is not *the* closest (Set 2 is ahead by 9) -- a conditional statement could be added to the end of the addition to ensure that the closest pair is noted as such (adding 8 to Set 1 would be appropriate in this case, with a difference of only 7 between the sets).  Because you are constrained to | n₁ - n₂ <= 1, I am fairly certain this is the best way to expect results.

To make incremental changes to see larger results than this, you can alternate the order in which the first elements are added.  For example, 1->Set 2, 2->Set 1, 3->Set 1, etc, then 1->Set1, 2->Set 1, 3->Set 2, 4->Set 2, 5->Set 1....  The difference between sums gets larger, of course, but you should have already determined the difference in sums.

[Chavo]

My current method for finding the top 1 combination is similar to a reversed ordered binary tree such that (using your example)

8-> Set 1
6-> Set 2
5-> Set 2
4-> Set 1
3-> Set 2
2-> Set 1
1-> Set 2 (because Set 1 has the highest single value, trivial though since they have equal before the value 1 is added)

where values are always added to the group with the lower total sum rather than a set order of adding to a certain group as you suggested.
The problem is it allows me very little flexibility in finding more than one arrangement.

[MyndFyre]

My current method for finding the top 1 combination is similar to a reversed ordered binary tree such that (using your example)

8-> Set 1
6-> Set 2
5-> Set 2
4-> Set 1
3-> Set 2
2-> Set 1
1-> Set 2 (because Set 1 has the highest single value, trivial though since they have equal before the value 1 is added)

where values are always added to the group with the lower total sum rather than a set order of adding to a certain group as you suggested.
The problem is it allows me very little flexibility in finding more than one arrangement.

I would caution you against unilaterally deciding that the last item goes into the tree without the single highest value.  you could have these numbers in place of 8, 6, and 5: 80,000, 79,999, and 79,998.  Clearly, 1 should go with the 80,000 set if possible.  Obviously this is not possible with datasets that have even numbers of components.

As I said, you should be able to produce similar sets with slightly larger sums by changing the order in which you add numbers. 

[Chavo]

Here's what I decided to do:

I start with a set containing all of the values which is then split into two arbitrary sets.

I add this first combination to a HashSet (duplicates are automatically removed and a primitive hash is calculated for every element)

I then add every other possible combination that has the same lengths for each set by swapping every element from set 1 with every element from set 2 recursively (I dont think this needs explaing, but I can if necessary).

Then it is a very simple matter of looping through the HashSet X times to find the best X combinations.

In my testing it took 16ms for my machine to do this for 20 values.