3

Given a list of integers l, how can I partition it into 2 lists a and b such that d(a,b) = abs(sum(a) - sum(b)) is minimum. I know the problem is NP-complete, so I am looking for a pseudo-polynomial time algorithm i.e. O(c*n) where c = sum(l map abs). I looked at Wikipedia but the algorithm there is to partition it into exact halves which is a special case of what I am looking for...

EDIT: To clarify, I am looking for the exact partitions a and b and not just the resulting minimum difference d(a, b)

To generalize, what is a pseudo-polynomial time algorithm to partition a list of n numbers into k groups g1, g2 ...gk such that (max(S) - min(S)).abs is as small as possible where S = [sum(g1), sum(g2), ... sum(gk)]

pathikrit
  • 32,469
  • 37
  • 142
  • 221
  • 2
    The editted question (generalization) completely changes thing. [k-partitioning](http://en.wikipedia.org/wiki/Partition_problem#The_k-partition_problem) is strong NP-Complete, and there is no known pseudo polynomial solution to it. – amit Apr 18 '14 at 20:26

3 Answers3

3

A naive, trivial and still pseudo-polynomial solution would be to use the existing solution to subset-sum, and repeat for sum(array)/2to 0 (and return the first one found).

Complexity of this solution will be O(W^2*n) where W is the sum of the array.

pseudo code:

for cand from sum(array)/2 to 0 descending:
   subset <- subsetSumSolver(array,cand)
   if subset != null:
        return subset

The above will return the maximal subset that is lower/equals sum(array)/2, and the other part is the complement for the returned subset.

However, the dynamic programming for subset-sum should be enough.

Recall that the formula is:

f(0,i) = true
f(x,0) = false | x != 0
f(x,i) = f(x-arr[i],i-1) OR f(x,i-1)

When building the matrix, the above actually creates you each row with value lower than the initial x, if you input sum(array)/2 - it's basically all values.

After you generate the DP matrix, just find the maximal value of x such that f(x,n)=true, and this is the best partition you can get.

Complexity in this case is O(Wn)

amit
  • 175,853
  • 27
  • 231
  • 333
  • But this just gives me x, what if I actually want to know what the partitions are?? – pathikrit Apr 18 '14 at 20:08
  • 1
    @wrick it is fairly easy to get the actual partition after this, just follow the table back from the given `x`, and check which 'decisions' you have made at each point. I once explained it for the similar knapsack algorithm in the thread: [How to find which elements are in the bag, using Knapsack Algorithm (and not only the bag's value)?](http://stackoverflow.com/q/7489398/572670). Try to follow that and let me now if you have any difficulties. – amit Apr 18 '14 at 20:22
  • @wrick For every 1 in the table, remember how it got there. – Niklas B. Apr 18 '14 at 20:35
0

You can phrase this as a 0/1 integer linear programming optimization problem. Let wi be the ith number, and let xi be a 0/1 variable which indicates whether wi is in the first set or not. Then you want to minimize sum(xi wi) - sum((1 - xi) wi) subject to

sum(xi wi) >= sum((1 - xi) wi)

and also subject to all xi being 0 or 1. There has been a lot of research into optimizing 0/1 linear programming solvers. For large total sum W this may be an improvement over the O(W n) pseudo-polynomial time algorithm presented because the W factor is scary.

user2566092
  • 4,631
  • 15
  • 20
-1

My first thought is to:

  1. Sort list of integers
  2. Create two empty lists A and B
  3. While iterating from biggest integer to smallest integer...add next integer to the list with the smallest current sum.

This is, of course, not guaranteed to give you the best result but you can bound the result it will give you by the size of the biggest integer in your list

Ivan
  • 1,256
  • 1
  • 9
  • 16
  • This is a non optimal greedy solution to subset-sum problem. The OP clarified he is looking for optimized solution and provided links for learning about the optimal solution. – amit Apr 18 '14 at 19:23
  • Bleh -- I saw pseudo and though pseudo optimal (not pseudo-polynomial) – Ivan Apr 18 '14 at 19:24
  • say you have a sequence of n numbers, the first n-1 with value k, the nth with value k(n-1). then your solution would be pretty suboptimal – ealfonso Nov 08 '15 at 21:19