Finding all partitions of a set s.t. each block contains exactly one subset from a given set of subsets - how hopeless?

Question

Hello and apologies if my question will be too elementary. My background is from arithmetic geometry, but I have been recently faced with certain computational problems of combinatorial nature, where I feel way out of my league, so I will definitely appreciate some clarity on the matter :)

Long story short, I am faced with the following type of a problem, which I would like to illustrate here with an example for the sake of better clarity:

Let $S:=\{1,2,...,42\}$ be a set of integers and let $N\subset\{T\in 2^S:|T|=3\}$ be fixed (pre-generated in a specific way). Typically, $|N|$ is in the order of 1500-2000. I would like to construct all 7-el. partitions $\Sigma=\{S_1,S_2,S_3,S_4,S_5,S_6,S_7\}$ of $S$ (i.e.$S_i\neq\emptyset$ for $i=1,...,7$ and $\cup_i S_i=S$) s.t. $|S_i|=6$ and $S_i$ contains exactly one element of $N$ as a subset, $i=1,...,7$. (*)

My question is, is this computationally feasible (e.g. a few days of number crunching on a modern workstation) by using an optimized routine/algorithm? And if yes, how?

In the particular example from above, a straightforward approach to obtain all 6-el. subsets of $S$ that contain exactly one element of $N$ as a subset yielded ~ 470 000 different subsets (also see this SO thread), which does not seem aproachable by a straightforward solution of the exact cover problem. Furthermore, in another example with $|S|=48$ and $|\Sigma|=8$, it yielded ~1.5 Mil different subsets.

Note that constructing all partitions, even with fixed block size, for sets with as many elements is kinda out of reach (cfg. Bell number or Stirling number of the 2nd kind). However, conjecturally, because of the specific nature of $N$ and the additional restriction on the blocks of the partition, it is expected that there are only very few such valid partitions (probably no more than 1 or 2). In other words, I am hoping that imposing the additional restriction (*) could be still used to obtain a suitable algorithm.

Since the underlying math for a potential proof or disproof may well be out of reach for now, I am hoping to at least get some computational verification for "larger" numbers before even attempting an attack on the mathematical part.

Thanks!

Answer 1

Here's an approach that I suspect will work very quickly.

I suggest you start by enumerating all possible values for an $S_i$, i.e., all possible 6-element subsets of $S$ that contain exactly one element of $N$ as a subset.

How many such sets do you expect to find? By a crude back-of-the-envelope estimate, I estimate there will be only a handful, maybe 10 of them are so. This estimate might be wrong, but this would be easy for you to test.

Let $\alpha$ be the number of possible such sets (i.e., $\alpha$ counts the number of ways to choose a 6-element subset of $S$ that contains exactly one element of $N$, i.e., there are $\alpha$ possible values for each $S_i$). I am predicting you'll find $\alpha \approx 10$, or something similarly small.

If this prediction is accurate, this suggests a simple, naive algorithm to enumerate the partitions: namely, enumerate all ${\alpha \choose 5}$ ways to choose five valid possibilities for the $S_i$, and check whether those five sets forms a partition. The running time of this algorithm is $O(\alpha^5)$. If $\alpha$ is very small, say $\alpha=10$, this will be plenty efficient.

If it turns out that $\alpha$ is a bit larger, you can optimize this naive algorithm a bit. Enumerate all ${\alpha \choose 2}$ ways to choose two out of these $\alpha$ 6-element sets, say $S_4,S_5$. Filter out pairs that have an overlap (i.e., an element of $S$ in common). Now store them in a hashtable, keyed by $S_4 \cup S_5$. The hashtable will contain $O(\alpha^2)$ entries and can be constructed in $O(\alpha^2)$ time. Next, enumerate all ${\alpha \choose 3}$ ways to choose $S_1,S_2,S_3$. If $S_1,S_2,S_3$ are pairwise disjoint, look up $S \setminus (S_1 \cup S_2 \cup S_3)$ in the hashtable to see whether there is pair $S_4,S_5$ that can be combined with $S_1,S_2,S_3$ to form a full partition of $S$. The running time of this optimized algorithm will be $O(\alpha^3)$.

And note that if $\alpha$ is indeed small, say $\alpha=10$ as I'm predicting, then it will be easy to enumerate all $\alpha$ possible values for an $S_i$. You just enumerate all possible elements of $N$, then try extending each with three more elements of $S$, one by one, testing each one to make sure that the resulting set does not contain any other element of $N$ as a subset. (In other words: select an element $T$ of $N$; select an element $x$ of $S \ T$, and check that $T \cup \{x\}$ does not contain any other element of $N$ as a subset; select an element $y$ of $S \setminus (T \cup \{x\})$, and check that $T \cup \{x,y\}$ does not contain any other element of $N$ as a subset; select an element $z$ of $S \setminus (T \cup \{x,y\})$, and check that $T \cup \{x,y,z\}$ does not contain any other element of $N$ as a subset. Each step is pretty easy to do, and the overall running time should be very fast, assuming that $\alpha$ is indeed small as I expect.)

So, I suggest you start by running a little experiment to measure $\alpha$, then see if any of these algorithms is fast enough. If it's not, edit your question to provide more details, including the value of $\alpha$.

---

Why do I estimate that $\alpha$ might be about 10? Here's my crude back-of-the-envelope calculation.

First off, there are ${30 \choose 6} \approx 2^{19}$ ways to choose a 6-element subset of $S$, and ${30 \choose 3} \approx 2^{12}$ ways to choose a 3-element subset of $S$. Therefore, $N$ contains about half of the possible 3-element subsets of $S$: in other words, if we pick a random 3-element subset of $S$, it'll be in $N$ with probability about 50% (roughly).

Also, for any 6-element subset $S_i$ of $S$, there are ${6 \choose 3} = 20$ ways to choose a 3-element subset of $S_i$, and each one has about a 50% chance of being an element of $N$. We want there to be exactly one 3-element subset of $S_i$ that is in $N$. This is like doing 20 coin flips, and we want to get exactly one heads (and the rest tails). The probability of that is ${20 \choose 1} \times 2^{-20}$, i.e., $20/2^{20}$. So, if we pick a 6-element subset of $S$, it will have probability about $20/2^{20}$ of being a valid possible value for some $S_i$.

Finally, there are $2^{19}$ possible 6-element subsets. So, we expect that about $2^{19} \times 20/2^{20} = 10$ of them will be a valid possible value for $S_i$. So, I'd expect $\alpha \approx 10$, using this crude argument.

This is a very crude estimate, because it assumes everything behaves randomly. It is not rigorous, both because your set $N$ might not be random; and also because I made independence assumptions all over the place, even though things are not independent. So, you will need to check empirically whether this estimate turns out to be accurate or not -- fortunately, that should be pretty easy to do.