2
$\begingroup$

I have an index taking as keys values from the power set $P(S)$ of a set $S$, except for $\emptyset$ and $S$.

Then I have a query $Q=(s, k)$, where $s \in P(S) - \{\emptyset \cup S\}$ and $ 1 < k \le |S|$.

The result of the query is the set of covers $R$ of $S$; $\forall r \in R, |r| \le k$.

So for instance, if $S = \{a, b, c, d\}$ and $Q=( \{a,b\}, 3 )$, $R$ should return all covers of $S$ formed by $\{a, b\}$ and $k = (3 - 1 = ) 2$ or less other subsets of $P(S) - \{\emptyset \cup S\}$, namely: $R = \{$ $$ \{a,b\} , \{c\} , \{d\}$$ $$ \{a,b\} , \{c, d\} $$ $$ \{a,b\} , \{a, c, d\} $$ $$ \{a,b\} , \{b, c, d\} $$ $\}$

I want to know if there is an efficient algorithm that can give me all of these combinations of covers.

In other words, I want to know if there is an efficient way to get all covers formed by at most $k$ elements, where I only know 1 element out of k.

$\endgroup$
  • $\begingroup$ There are others such as $\{a,b\},\{a,c\},\{d\}$, indeed $15$ others. $\endgroup$ – Yuval Filmus Sep 18 '13 at 19:18
2
$\begingroup$

The first step is to eliminate the known set $s$. The idea is to find all covers of $S \setminus s$ using at most $k-1$ sets, and then augment the solution by adding all subsets of $s$ to all sets in any given cover in all possible ways. Details omitted.

For the new problem, it is enough to find all covers of $S$ of size exactly $k$ which don't use $S$ or $\emptyset$. In fact, we can ignore these restrictions, and just drop the (relatively) few solutions using these sets. We will generate them ordered, incurring a factor of $k!$ in efficiency; I'm sure that can be avoided, but I'll leave the details for you. Consider the sets $S_1,\ldots,S_k$ in order, and suppose that they cover $a_1,\ldots,a_k$ "new" elements, that is $|S_1| = a_1$, $|S_2 \setminus S_1| = a_2$ and so on. Then $a_1 + \cdots + a_k = |S|$, and we can enumerate over all such sequences (including zeroes). For each sequence, we can enumerate over the new elements themselves. Finally, we enumerate over all possible ways of adding "old" elements to sets, for example $S_3$ could additionally to $a_3$ new elements contain any subset of $S_1 \cup S_2$.

$\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.