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

Roomful

Isn't this (or at least 2-partition) NP-complete? – Evidently

For arbitrary-size integers; yes it is. The copy-pasted question probably mentions that limitation after runs in time poly- nomial in n and, I'd presume. – Yandell

You were missing a crucial part (I added it). It is polynomial in n and Sum a_i. If you don't include the sum a_i, the problem is actually NP-Hard. – Tentation

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

Reremouse

The complexity is a bit higher than you say if there are negative numbers, but that's a detail. – Yandell

@Nikita, Can you please elaborate? I'm familiar with 2-Partition...but I didn't understand how the 2D boolean array was created...and what it represented... – Marrissa

@Marrissa sums[i][j] tells whether it's possible to split original set into 3 subsets, first with sum i and second with sum j (and third, obviously, with sum TOTAL - i - j). Does it help? – Reremouse

@Nikita, Yes, i do understand it, but i can't figure out how to implement it? Is there any implementation i can refer? I'd be grateful. – Marrissa

@Marrissa Ok, if you give me a pseudocode of 2p solution as you see it (paste it on the web somewhere and leave a link), I can easily turn it into 3p solution. They're really the same. – Reremouse

@Nikita, Thanks, here you go, it's a C++ implementation. pastie.org/1762720 – Marrissa

@NikitaRybak you should check for the conditions in your code that j + C[i] <=N and for other one also . and also return T[N/3][N/3] – Lippert

for some reason pastie.org doesn't work and i'm still confused, how to do you check and rotate elements in a S[i, j] sets to check? how do you track back to get actual items of 3 lists? @NikitaRybak – Shwa

@Marrissa can you explain the solution? pastie doesn't work anymore, and description still doesn't give me a clue. Thanks! – Shwa

@Marcello Pastie seems to be down, but archive.org is here to save the day: web.archive.org/web/20151031213948/pastie.org/1762895#8,12 (that said, the code has at least two bugs and just doesn't work, I'm sorry to say). – Eucaine

So if there are k partitions, you should be creating a multidimensional array of dimensions (n * sum(w)/k * sum(w)/k * sum(w)/k * sum(w)/k .... k-1 times). I see a different intuition used to solve the same problem here - github.com/anoubhav/Coursera-Algorithmic-Toolbox/blob/master/… where he just uses as 2-dimensional array of size (n * sum(w)/k) – Inconsumable

Answer 2

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.

Bunde

Answer 3

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.

Yandell

Answer 4

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];
}

Ischia

Answer 5

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 )

Chancy

Answer 6

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;
}

Herzl

Answer 7

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);
}

Heimer

This does not provide an answer to the question. Once you have sufficient reputation you will be able to comment on any post; instead, provide answers that don't require clarification from the asker. - From Review – Jacobs

Answer 8

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.

Photogene