2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Please don't add "edit: the above is incorrect" to the question. Instead, edit the question to reflect what it should have been, so that when a new reader reads it for the first time, they have a clean polished question. (We have a revision history built into this web site, so you don't need to retain what the prior revision looked like.) P.S. What do you mean by "best case" and "worst case" in the last paragraph? Also, can you elaborate on the relationship to exact cover that you see? $N$ is fixed (part of the input), so I'm not immediately seeing how exact cover applies. $\endgroup$ – D.W. Aug 29 '14 at 5:00
  • $\begingroup$ Thanks for the remarks, it should be fixed now together with some clarifications. Typically, $|S|$ is in the interval 40-50, while $|\Sigma|$ range is then 7,8 (since all blocks of the partition have equal size, it must be a divisor of $|S|$). By "best case" and "worst case" I simply meant the lowest and highest number of possible 6-el. subsets of $S$ that contain exactly one element from $N$ when $S$ varies. It should be clear in the new edit. $\endgroup$ – M.G. Aug 29 '14 at 5:29
  • $\begingroup$ Once you have the possible 6-el. subsets of $S$ that contain exactly one el. from $N$, finding which groups of them constitute a partition of $S$ is just a special case of the exact cover problem, no? $\endgroup$ – M.G. Aug 29 '14 at 5:30
  • $\begingroup$ How many conflict-free $|\Sigma|$-tuples over $N$ are there? If their number is small, it might be feasible to start from them. If it is large, then the set you want to enumerate will most likely be too large to handle. $\endgroup$ – FrankW Sep 4 '14 at 12:42
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for your reply! And apologies that I cannot upvote it as I don't have enough reputation to do so. In my concrete application, $S$ has a size between 40 and 50, I can see now that my example was a little misleading in that regard, I will update my post to account for that. In the best case with $|S|$ being close to 40, the number of all possible 6-element subsets of $S$ that contain exactly one element of $N$ as a subset was in the order of 400 000 :) Hence my problem with it. $\endgroup$ – M.G. Aug 28 '14 at 21:19
  • $\begingroup$ ...and sincere apologies for the "belated" accepting of your answer! $\endgroup$ – M.G. Jun 27 '18 at 22:32

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.