3-PARTITION problem

Question

here is another dynamic programming question (Vazirani ch6)

Consider the following 3-PARTITION problem. Given integers a1...an, we want to determine whether it is possible to partition of {1...n} into three disjoint subsets I, J, K such that

sum(I) = sum(J) = sum(K) = 1/3*sum(ALL)

For example, for input (1; 2; 3; 4; 4; 5; 8) the answer is yes, because there is the partition (1; 8), (4; 5), (2; 3; 4). On the other hand, for input (2; 2; 3; 5) the answer is no. Devise and analyze a dynamic programming algorithm for 3-PARTITION that runs in time poly- nomial in n and (Sum a_i)

How can I solve this problem? I know 2-partition but still can't solve it

Answer 1

It's easy to generalize 2-sets solution for 3-sets case.

In original version, you create array of boolean sums where sums[i] tells whether sum i can be reached with numbers from the set, or not. Then, once array is created, you just see if sums[TOTAL/2] is true or not.

Since you said you know old version already, I'll describe only difference between them.

In 3-partition case, you keep array of boolean sums, where sums[i][j] tells whether first set can have sum i and second - sum j. Then, once array is created, you just see if sums[TOTAL/3][TOTAL/3] is true or not.

If original complexity is O(TOTAL*n), here it's O(TOTAL^2*n).
It may not be polynomial in the strictest sense of the word, but then original version isn't strictly polynomial too :)

Answer 2

If this problem is to be solvable; then sum(ALL)/3 must be an integer. Any solution must have SUM(J) + SUM(K) = SUM(I) + sum(ALL)/3. This represents a solution to the 2-partition problem over concat(ALL, {sum(ALL)/3}).

You say you have a 2-partition implementation: use it to solve that problem. Then (at least) one of the two partitions will contain the number sum(ALL)/3 - remove the number from that partion, and you've found I. For the other partition, run 2-partition again, to split J from K; after all, J and K must be equal in sum themselves.

Edit: This solution is probably incorrect - the 2-partition of the concatenated set will have several solutions (at least one for each of I, J, K) - however, if there are other solutions, then the "other side" may not consist of the union of two of I, J, K, and may not be splittable at all. You'll need to actually think, I fear :-).

Try 2: Iterate over the multiset, maintaining the following map: R(i,j,k) :: Boolean which represents the fact whether up to the current iteration the numbers permit division into three multisets that have sums i, j, k. I.e., for any R(i,j,k) and next number n in the next state R' it holds that R'(i+n,j,k) and R'(i,j+n,k) and R'(i,j,k+n). Note that the complexity (as per the excersize) depends on the magnitude of the input numbers; this is a pseudo-polynomialtime algorithm. Nikita's solution is conceptually similar but more efficient than this solution since it doesn't track the third set's sum: that's unnecessary since you can trivially compute it.

Answer 3

Another example in C++ (based on the previous answers):

bool partition3(vector<int> const &A) {
  int sum = 0;
  for (int i = 0; i < A.size(); i++) {
    sum += A[i];
  }

  if (sum % 3 != 0) {
    return false;
  }

  vector<vector<vector<int>>> E(A.size() + 1, vector<vector<int>>(sum / 3 + 1, vector<int>(sum / 3 + 1, 0)));

  for (int i = 1; i <= A.size(); i++) {
    for (int j = 0; j <= sum / 3; j++) {
      for (int k = 0; k <= sum / 3; k++) {
        E[i][j][k] = E[i - 1][j][k];
        if (A[i - 1] <= k) {
          E[i][j][k] = max(E[i][j][k], E[i - 1][j][k - A[i - 1]] + A[i - 1]);
        }

        if (A[i - 1] <= j) {
          E[i][j][k] = max(E[i][j][k], E[i - 1][j - A[i - 1]][k] + A[i - 1]);
        }
      }
    }
  }
  
  return (E.back().back().back() / 2 == sum / 3);
}

Answer 4

I think by reduction it goes like this:

Reducing 2-partition to 3-partition:

Let S be the original set, and A be its total sum, then let S'=union({A/2},S). Hence, perform a 3-partition on the set S' yields three sets X, Y, Z. Among X, Y, Z, one of them must be {A/2}, say it's set Z, then X and Y is a 2-partition. The witnesses of 3-partition on S' is the witnesses of 2-partition on S, thus 2-partition reduces to 3-partition.

Answer 5

Create a three dimensional array, where size is count of elements, and part is equal to to sum of all elements divided by 3. So each cell of array[seq][sum1][sum2] tells can you create sum1 and sum2 using max seq elements from given array A[] or not. So compute all values of array, result will be in cell array[using all elements][sum of all element / 3][sum of all elements / 3], if you can create two sets without crossing equal to sum/3, there will be third set.

Logic of checking: exlude A[seq] element to third sum(not stored), check cell without element if it has same two sums; OR include to sum1 - if it is possible to get two sets without seq element, where sum1 is smaller by value of element seq A[seq], and sum2 isn't changed; OR include to sum2 check like previous.

int partition3(vector<int> &A)
{
    int part=0;
    for (int a : A)
        part += a;
    if (part%3)
        return 0;
    int size = A.size()+1;
    part = part/3+1;
    bool array[size][part][part];
    //sequence from 0 integers inside to all inside
    for(int seq=0; seq<size; seq++)
        for(int sum1=0; sum1<part; sum1++)
            for(int sum2=0;sum2<part; sum2++) {
                bool curRes;
                if (seq==0)
                    if (sum1 == 0 && sum2 == 0)
                        curRes = true;
                    else
                        curRes= false;
                else {
                    int curInSeq = seq-1;
                    bool excludeFrom = array[seq-1][sum1][sum2];
                    bool includeToSum1 = (sum1>=A[curInSeq]
                                          && array[seq-1][sum1-A[curInSeq]][sum2]);
                    bool includeToSum2 = (sum2>=A[curInSeq]
                                          && array[seq-1][sum1][sum2-A[curInSeq]]);
                    curRes = excludeFrom || includeToSum1 || includeToSum2;
                }
                array[seq][sum1][sum2] = curRes;
            }
    int result = array[size-1][part-1][part-1];
    return result;
}

Answer 6

You really want Korf's Complete Karmarkar-Karp algorithm (http://ac.els-cdn.com/S0004370298000861/1-s2.0-S0004370298000861-main.pdf, http://ijcai.org/papers09/Papers/IJCAI09-096.pdf). A generalization to three-partitioning is given. The algorithm is surprisingly fast given the complexity of the problem, but requires some implementation.

The essential idea of KK is to ensure that large blocks of similar size appear in different partitions. One groups pairs of blocks, which can then be treated as a smaller block of size equal to the difference in sizes that can be placed as normal: by doing this recursively, one ends up with small blocks that are easy to place. One then does a two-coloring of the block groups to ensure that the opposite placements are handled. The extension to 3-partition is a bit complicated. The Korf extension is to use depth-first search in KK order to find all possible solutions or to find a solution quickly.

Answer 7

As I have answered in same another question like this, the C++ implementation would look something like this:

int partition3(vector<int> &A)
{
  int sum = accumulate(A.begin(), A.end(), 0);
  if (sum % 3 != 0)
  {
    return false;
  }
  int size = A.size();

  vector<vector<int>> dp(sum + 1, vector<int>(sum + 1, 0));
  dp[0][0] = true;

  // process the numbers one by one
  for (int i = 0; i < size; i++)
  {
    for (int j = sum; j >= 0; --j)
    {
      for (int k = sum; k >= 0; --k)
      {
        if (dp[j][k])
        {
          dp[j + A[i]][k] = true;
          dp[j][k + A[i]] = true;
        }
      }
    }
  }
  return dp[sum / 3][sum / 3];
}

Answer 8

Let's say you want to partition the set $X = {x_1, ..., x_n}$ in $k$ partitions. Create a $ n \times k $ table. Assume the cost $M[i,j]$ be the maximum sum of $i$ elements in $j$ partitions. Just recursively use the following optimality criterion to fill it:

M[n,k] = min_{i\leq n}  max ( M[i, k-1], \sum_{j=i+1}^{n} x_i ) 

Using these initial values for the table: 

M[i,1] = \sum_{j=1}^{i} x_i  and  M[1,j] = x_j  

The running time is $O(kn^2)$ (polynomial )