<p>(Pardon me for any unrefined usage/terminology for I do not have a math/CS background.)
Consider a collection of $N$ balls with subsets of $n_1, n_2, ..., n_L$ balls of different $L$ colors. The problem is to partition the $N$ balls into $M$ equal-sized groups (given $(N\mod M)=0$) such that the color subsets are preserved within new groups <em>as much as possible</em>. In the scenarios I'm concerned with, you could assume that for all $L$ original subsets, $n_l &lt; (N/M)$.</p>

<p>Here's an example to make the problem clear:
For a collection of $12$ balls with $4$ color-subsets - $\{1111\}$, $\{222\}$, $\{33\}$, $\{444\}$ - that needs to be split into 2 groups, the best way to do so is $\{111133\}$ and $\{222444\}$</p>

<ol>
<li>Is this problem well-defined?</li>
<li>Is there an algorithm to solve this problem exactly in polynomial time?</li>
<li>If not, is there an approximate algorithm?</li>
</ol>

CC BY-SA 3.0
2011-11-10T22:56:59.403Z
I think you'll need to be precise about "preserved as much as possible". Is there a penalty function ?
Suresh Venkat
CC BY-SA 3.0
2011-11-17T23:25:51.977Z
I do not have any concrete penalty function in mind, except that this function has to be an increasing function of the number (and size?) of splits of the same-colored subsets. For instance, a subset of 10 blue balls is could receive increasing penalty in the following order: {10} < {9,1} < {8,2} <(?) {8,1,1} < ... I see that this may be related to partition functions, but I'm not sure.
Arjun Krishnan
CC BY-SA 3.0
2011-11-18T04:36:01.233Z
that's not really enough. I think just for clarity you need to define for a given solution how to compute its cost. it doesn't have to be exactly what you had in mind as long as it emphasizes the right "trends"
Suresh Venkat
<co.combinatorics>
Regrouping a collection of sets based on constraint
Arjun Krishnan
# Regrouping a collection of sets based on constraint

(Asked by: username_0 on 2011-11-10)

(Pardon me for any unrefined usage/terminology for I do not have a math/CS background.)
Consider a collection of $N$ balls with subsets of $n\_1, n\_2, ..., n\_L$ balls of different $L$ colors. The problem is to partition the $N$ balls into $M$ equal-sized groups (given $(N\mod M)=0$) such that the color subsets are preserved within new groups *as much as possible*. In the scenarios I'm concerned with, you could assume that for all $L$ original subsets, $n\_l < (N/M)$.

Here's an example to make the problem clear:
For a collection of $12$ balls with $4$ color-subsets - $\{1111\}$, $\{222\}$, $\{33\}$, $\{444\}$ - that needs to be split into 2 groups, the best way to do so is $\{111133\}$ and $\{222444\}$

1. Is this problem well-defined?
2. Is there an algorithm to solve this problem exactly in polynomial time?
3. If not, is there an approximate algorithm?

**Tags:** co.combinatorics
> **Comments:**
> **username_1**: I think you'll need to be precise about "preserved as much as possible". Is there a penalty function ?  
> **username_0**: I do not have any concrete penalty function in mind, except that this function has to be an increasing function of the number (and size?) of splits of the same-colored subsets. For instance, a subset of 10 blue balls is could receive increasing penalty in the following order: {10} < {9,1} < {8,2} <(?) {8,1,1} < ... I see that this may be related to partition functions, but I'm not sure.  
> **username_1**: that's not really enough. I think just for clarity you need to define for a given solution how to compute its cost. it doesn't have to be exactly what you had in mind as long as it emphasizes the right "trends"  

---

## 0 answers

