0
$\begingroup$

Sorry for the vague title but I'm not familiar with the area and don't know what the right termilogy might be.

The problem I'd like to solve is: Given a collection $S$ of all the size $k$-subsets of the set $N=[1,\cdots,n]$, where $k\leq n$, find the partitions $S_i$ of $\mathcal{S}$ such that each $S_i$ covers $N$, where $S_i \bigcap S_j = \varnothing$ if $i\neq j$, and $\bigcup S_i=S$.

There are $\binom{n}{k}$ members in $S$.

An example is: $N=\{1,2,\cdots,4\}$, $k=2$, so $S=\{ \{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\} \}$, and a partition would be

$S_1=\{ \{1,2\},\{3,4\} \}$

$S_2=\{ \{1,3\},\{3,4\} \}$

$S_3=\{ \{1,4\},\{2,3\} \}$

I see that the $k$-disjoint set cover problem is NP-complete, but this problem can be seen as a special case where the set $S$ is given as above.

I appreciate it if there are any suggestions on possible directions to solve the problem. Thank you.

$\endgroup$
4
  • 1
    $\begingroup$ What exactly do you want? A formula for the number of partitions? An algorithm to generate them? $\endgroup$ Feb 11 '19 at 15:47
  • $\begingroup$ @PeterTaylor Hi Peter, thanks for your comment. Yes I'd like an algorithm to generate these partitions if available. If generating them is NP-hard, then it'd be better if I can prove it.. $\endgroup$
    – J Zhao
    Feb 11 '19 at 16:01
  • $\begingroup$ It seems that you are looking for the number of partitions of the set $N$ into subsets of size $k$ only (of course with $k | n$), is it so ? $\endgroup$
    – G Cab
    Feb 11 '19 at 16:59
  • $\begingroup$ @GCab Thanks. I think the number of partitions is $\frac{\binom{n}{k}}{\text{cardinality of each partition}}$, and the cardinality of each partition can be decided by $\frac{n}{k}$ in certain cases. I'm more concerned about generating these partitions. Thank you again. $\endgroup$
    – J Zhao
    Feb 11 '19 at 17:20
2
$\begingroup$

The algorithm is simple: to partition $N$ into subsets of size $k$ pick an arbitrary element $x \in N$. Then for each of the $\binom{|N| - 1}{k-1}$ subsets $s$ of size $k$ which contain $x$, recur on $N \setminus s$.

This also gives a simple formula for the number of ways of partitioning $kd$ elements into subsets of size $k$: $$\prod_{i=1}^d \binom{ki-1}{k-1} = \frac{1}{(k-1)!^d} \prod_{i=1}^d\frac{(ki-1)!}{(k(i-1))!} = \frac{(kd-1)!}{(k-1)!^d \prod_{i=1}^{d-1} ki} = \frac{k(kd-1)!}{k!^d (d-1)!} $$

By Stirling's formula $n! \approx \sqrt{2\pi n} \left(\frac n e\right)^n$, this is approximately $$\frac{e^d (kd-1)^{kd-1/2}}{(\sqrt{2\pi})^{d} k^{kd+d/2-1} (d-1)^{d-1/2}} \approx \left(\frac{e d^{(k-1)}}{\sqrt{2\pi k}}\right)^d$$ which is most certainly not polynomial in $d$, so generating all of the solutions is not in NP.

$\endgroup$
0
$\begingroup$

You need $k$ to divide $n$ to make this work at all. In that case you are breaking the $n$ items into groups of $k$. You can do this in $\frac {n!}{(k!)^{n/k}\left(\frac nk \right)!}$ ways. You can think of putting them in a line, which you can do in $n!$ ways and cutting the line into groups of $k$. There are $\frac nk$ groups. Each one can be reordered in $k!$ ways, then the groups can be reordered in $\left(\frac nk \right)!$ ways, which gives the denominator.

$\endgroup$

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.