Finding smallest delta available for permutations of a set of numbers

Question

Presume we have a set of 12 objects, lets say {1,2,3,4,5,6,7,8,9,10,11,12}. We must break this set into 4 smaller ones composed of three objects, so that the largest sum and smallest sum of these four sets is minimized. We must find this difference. In our example, {1,7,12},(3,8,9},{4,5,10},{2,6,11}. These four sets satisfy the problem since their sums are 20 and 19, meaning a delta of 1, our answer.

How can one solve this problem for any arbitrary 12 values?

I've tried enumerating all partitions of said set into 4 sets of 3, and finding one with the optimal score. However, time is of the essence, and so I was wondering how one would approach this problem in Java

I don't have exact code on me right now, but what it essentially was was 9 nested for loops, where the first three that nest are one set, the next three are the next set, the last three are another set, and the three left overs are another set. I used a 2D array so that values would be in score[i][0] and score[i][1] would act as an indicator to let me know if that value in score[i][0] had already been placed into a set.

This of course gets tedious and inefficient.

Answer 1

You could easily simplify the problem by finding the values that the sums must approach for a better optimisation :

For instance, in your simple case (1,2...12), then the total sum of every terms is 78. Thus, Each groups must have a sum very close to 78/4=19.

So, let's try a very simple algorithm :

- compute TOTAL_SUM = SUM(terms)
- compute TARGET_SUM = TOTAL_SUM / number(terms)
- set DELTA=0
- loop {
-    Try to split terms in groups where TARGET_SUM - DELTA <= SUM <= TARGET_SUM + DELTA
-    if a solution is found, exit
-    DELTA = DELTA + 1
-    }

Ok, I did not helped you much with this "Try to split..." step. But it should look like you own solution, except that you have additional constraints which can help you to speed up the process.

Hope this helps.