I have to solve the following problem:

Given a set of + and - elements, I have to split this set into n sets. These subsets must meet the following requirements:

  1. All will have similar number of elements (similar means that will differ in 0 or 1 elements).
  2. All will have the same proportion of + and - elements than in the original set.

I have a set with 11 elements, (- - - - - - - + + + +), with 7 - and 4 +, and I have to split it into 3 subsets.

I know how to do the first point. I will have three subsets with 4 elements, 4 elements and 3 elements. I have test my formulas with many sizes and it works perfectly.

My problem comes with keeping the same proportion. This is what I did:

  1. I have divided the number of elements in the set by the number of - elements and + elements.

7 / 11 = 0.64. 64% of the elements are -. 4 / 11 = 0.36. 36% of the elements are +.

  1. I have multiplied this proportion with the number of elements on each subset.

4 * 0.64 = 2.56 - elements. 4 * 0.36 = 1.44 + elements.

  1. I can't add 2.56 elements, so I have decided to round up the bigger number, and to floor the smallest one.

2.56 => 3 - elements. 1.44 => 1 + elements.

The next subset, with 4 elements, will have:

3 - elements. 1 + elements.

And the latest one, with 3 elements, will have:

3 * 0.64 = 1.92 => 2 - elements. 3 * 0.36 = 1.08 => 1 + elements.

But if you add all of the elements on each subset, you will get:

3 + 3 + 2 = 8 - elements. 1 + 1 + 1 = 3 - elements.

Which is wrong.

How can I fix this error?

  • 1
    It's not possible to satisfy condition (2) unless the number of $+$'s and number of $-$'s are both multiples of the number $n$ of subsets into which we're dividing (or if the number of $+$'s or number of $-$'s is zero). – Travis Nov 8 at 19:20

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.