[Solved]: Partition partition with constraint of equal size

Problem Detail: 

I see the problem here which is the well know partition problem but with constraint that the size of both sets must be equal.

I look at the answer and I don't understand that why Colin said add max(S)⋅length(S), and run the algorithm as normal would make the size of both sets equal. I think for long time.

And i think that his claim for send s∈S to 1+s⋅length(S) is wrong?

Example:

Initial set: 1 2 3 9

1+s⋅length(S)= 1+s(4)=5 9 13 37

After running the traditional Boolean algorithm, what I got is one set of 5 9 13, another set of 37?

Can anyone explain to me? Especially the max(S)⋅length(S) one.

Asked By : user196736

Answered By : rotia

The idea of Colin's algorithm is to try to force a multiset that has partitions where the cardinality of the subset is different, to have only partitions where the resulting subsets have the same size. So that the problem can only be solved if we can divide the multiset into two subsets with the same cardinality

For instance, think in the multiset

{1,1,1,2,2,3}.

This set has more than one way of partitioning it:

We can partition it into {3,1,1} and {2,2,1}

Or we can partition it into {1,1,1,2} and {3,2}

In the variant they talk about, only the first way to partition this multiset is valid.

So, what he does is adding to each number the following quantity:

Number + (number with highest value * cardinality of the set we want to divide)

In our example this results in:

{19,19,19,20,20,21}

And we can only partition this multiset of numbers only if we can partition it into two subsets with the same cardinality, in this case:

{19,20,20} and {19,19,21}

Why does it work?

It works because you add to each number the same quantity, so in a partition where the two subsets have the same cardinality, we add the number the same number of times to each subset, in a partition with subsets of different cardinality, we add the number to each subset a number of times that is not equal, so the subsets can't have the same sum.

For instance

We keep with the previous example

1 + 18 + 2 + 18 + 2 + 18

and

1 + 18 + 1 +18 + 3 +18

This partition has the same sum because we add the number eighteen three times to each subset.

But

1 + 18 + 1 +18 + 1 +18 + 2 + 18

and

3 + 18 + 2 +18

don't give the same result because we add eighteen to the first subset four times and only two to the other subset, as the two had the same sum before the transformation, by adding a number to each subset a number of times that is not equal, the two don't have the same sum anymore

Hope this is helpful

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33697