The Partition problem

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

{开发者_C百科 10, 200 } { 20, 90, 100 }

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.

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).

If you have it working in general and you're just looking for deterministic behaviour regardless of the order, just sort the set first. All sets that are the same disregarding order will be the exact same sequence after being sorted.

Of course it might inflate your runtime complexity but I didn't see that preventing this was a requirement.

All this is based on your comment that the arrangement of numbers truly doesn't matter. At that point this certainly isn't the same as the problem you linked to, which assumes that the partitions never require rearranging the elements.

LeetCoder have worked on the same problem definition (and solution) provided by Steven Skiena. Only thing is that he talks in C++, so it becomes some what easier to grasp.