1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why is this not a comment beneath the answer there? $\endgroup$ – Raphael Dec 1 '14 at 18:20
  • $\begingroup$ Sorry Raphael, I am new here. I thought the old post is too old that it is closed. $\endgroup$ – user196736 Dec 2 '14 at 5:06
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This is where I got stuck..how to prove that after adding max(S)⋅length(S), the partition must be equal size? Where does the max(S)⋅length(S) comes from? Why adding 1 doesn't do the trick? $\endgroup$ – user196736 Dec 2 '14 at 5:08
  • $\begingroup$ Adding one doesn't do the trick because you can have a partition like 1,1,1,2,2,3,15, which can't be partitioned, converted into 2,2,2,3,3,4,16 that can be partitioned into 2,2,2,3,3,4 and 16 $\endgroup$ – rotia Dec 2 '14 at 10:24
  • $\begingroup$ I know adding 1 doesn't do the trick, but why adding max(S)⋅length(S) do the trick? How do I prove it adding max(S)⋅length(S) do the trick in any situation/for any set? $\endgroup$ – user196736 Dec 2 '14 at 12:15
  • $\begingroup$ You add max(S) * lenght(S) to each number, because that will be the biggest number that you can create with a set of that size if max(S) is the biggest number, so that you can't ever sum two or more smaller numbers to get to one bigger, i put you an example 1,1,2, using this trick you can't never get to two because 1+6 + 1+6 are bigger than 2+6 $\endgroup$ – rotia Dec 2 '14 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.