Suppose that there are $k$ sets $S_1, S_2, S_3, \dots, S_k$.

The numbers $N = \{1, 2, \dots,n\}$ are distributed into these sets equally.

Say that we partition $N$ into $m$ sets $P_1, P_2, \dots, P_m$.

The problem is to find how accurate is our partitioning. However, the accuracy is not finding the exact same sets, but putting the same elements into the same set. For instance:

$S_1 = \{1,2,3,4,5,6\}$
$S_2 = \{7,8,9,10,11,12\}$
$S_3 = \{13,14,15,16,17,18\}$


$P_1 = \{1,2\}$
$P_2 = \{3,4,5\}$
$P_3 = \{6,7,8,9\}$
$P_4 = \{10,11,12\}$
$P_5 = \{13,14,15,16\}$
$P_6 = \{17\}$
$P_7 = \{18\}$

This partitioning is almost accurate because if we were to put $6$ into $P_2$ instead of $P_3$, then none of the sets would contain elements those do not belong to the same set in the original sets.

$P_1 = \{1,2,3,4,5,6,7,8,9\}$
$P_2 = \{10,11,12,13,14,15,16,17,18\}$

is a very inaccurate partitioning because half of the elements in each set is from a different set.

My questions are:
1. Is there a name for this problem?
2. Is this problem NP-Hard?
3. How can I define a metric for the accuracy of the partitioning?
4. How can I find how accurate a partitioning is?

  • $\begingroup$ You really need to formally define "accuracy" to give this problem a meaning. We can't discuss hardness till the decision problem is well-defined. $\endgroup$ – R B Jan 14 '15 at 21:36

Your Answer

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

Browse other questions tagged or ask your own question.