The Partition problem

Question

I have set of non-unique numbers and would like to partition those numbers into K partitions such that sum of numbers in each partition is almost equal . Assume I have following set.

{1, 2, 3, 4, 5, 6, 7, 8, 9}

Using Linear partition algorithm I get following partitions when K = 3

{ 1  2  3  4  5 }
{ 6  7 }
{ 8  9 }

Which is expected, but since this is linear partitioning algorithm , any change in the order of the input set will change the partitions also, which I want to avoid.

Difference of Sum of elements for each partition should be minimized. In above example Sum of each partitions is 15 , 13, 17

for following input it does not work.

{10, 20, 90, 100, 200}

Linear partition algorithm gives me following

{ 10  20  90  100 }
{ 200 }

But correct answer should be

{ 10, 200 } { 20, 90, 100 }

Answer 1

Here is a fast greedy solution (near-optimal for most cases):

1. Sort the elements in descending order
2. Take the first K elements and put them into different sets
3. For the next N-K elements, put them in the set with the lowest sum

In your case with {10, 20, 90, 100, 200}, after sorting you get {200, 100, 90, 20, 10}. The algorithm will step through as follows:

Set A   Set B
 200     100
 200     190
 200     210
 210     210

which happens to be the optimal solution.

Answer 2

I think that pretty much the only option you have is to use brute force, possibly with some optimizations (like a modified version of the pseudo-polynomial solution to subset sum problem for K = 2) for simple cases. Maybe there is a better algorithm, but not much better.

From reading the Wikipedia articles on Partition problem and 3-partition problem, I get that your problem is generalized and slightly modified version of these problems, that are NP-complete.

More specifically, if you had an efficient algorithm for solving your problem, it would also be able to efficiently solve the two problems above, which is impossible (unless P = NP).