Generating sets of tuples from possible candidate lists (or finding perfect matchings in uniform hypergraphs)

Question

First, apologies for the title. This is an odd question, and I couldn't come up with a simple title for it.

I'm trying to come up with a good algorithm for the following, and it's giving me a headache.

I have (not necessarily disjoint) sets $S_1,\ldots,S_T$, each $S_t$ contains a subset of $1,\ldots,N$ for some $N$. I want to generate all possible objects, where an object is defined as a set of $k$ tuples of length $T$, with each tuple in an object containing exactly one element from each of $S_1,\ldots,S_T$ and in each object no base element from $1,\ldots,N$ is repeated.

For example: $k = 3, T = 2, N = 6$.

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

$S_2 = \{2,3,4,6\}$

One valid object would be $O_1 = (1,2),(4,3),(5,6)$ - all six numbers appear and each pair has one element from $S_1$ and one element from $S_2$. EDIT: I had before that $O_1 = (1,2),(3,4),(5,6)$. This was incorrect.

An invalid object would be $(1,5),(2,4),(3,6)$, since $1 \in S_1$ but $5 \notin S_2$.

The reason I'm interested in this is because these valid objects are feasible solutions for a problem I'm working on, and I'd like to enumerate all feasible solutions on small test cases to get some intuition on my problem.

One more edit: Thanks to the help of Aaron Meyerowitz, It seems to be that this problem can be thought of as the problem of finding perfect matchings in a $T$-uniform hypergraph on $N$ nodes. I'll leave it open a bit more with the hope that it's easier and not equivalent to this problem, but just learning this much about it is helpful.

Answer 1

Here is a possible title matchings in hypergraphs This is just a restatement but it might help with finding references. For $T=2$ one has the usual graphs and there are good algorithms for finding maximum size matchings. For larger $T$ finding matchings is (in general) NP-complete even for $T=3$. It may be that there are special features of your problem that bring things into reach.

For $T=2$ make a simple undirected graph with vertices $1,\cdots,N$ and edges all pairs $(i,j)$ which are allowed ($i \in S_1 \text{ and } j \in S_2$ or vice versa). A matching is a set of vertex disjoint edges (also called an independent edge set). If $KT=N$ then you are asking for a perfect matching.

If $T>2$ one can consider a hypergraph whose hyper-edges are all legal $T$-tuples and look for a matching.

Of course it is more compact to list your sets $S_i$ than to list every possible $T$-tuple. Your example above is the complete graph $K_6$ missing only the edges $(1,5)$ and $(3,6).$ The full graph $K_6$ has $15$ perfect matchings, $3$ using each edge. Of these, $10$ work for your problem.

Here is a slightly more promising idea: Make a bipartite graph with $N+T$ vertices labelled $1,\cdots,N$ on one side and $S_1,\cdots,S_T$ on the other. Draw an edge for $j$ to $S_t$ when $j \in S_t$. Then a maximum size matching of this graph would have at best $T$ edges. So you could look for $k$ disjoint $T$-matchings. This has the added structure that each tuple is essentially ordered.

---

Later thoughts: You've changed the problem to clarify that the tuples are ordered.

An answer might depend on $k$ and $T$. For $T=2$ you could use the first idea of matchings with unordered pairs in a possibly non-bipartite graph. For each solution find out how many of the pairs have both members in $S_1 \cap S_2$. If the number is $j$ then this gives $2^j$ ordered solutions.

If $T$ is large Then you might look to choose $k$ elements from each set so as to get $kT$ elements. Each such choice would describe $(k!)^{T-1}$ solutions. So now your example has 12 solutions because for the two solutions (24)(13)(56) and (24)(16)(53) can each replace (24) with (42). This number is also $\mathbf{2}*3!$ since from $S_1$ you must choose $1,5$ and from $S_2$ $3,6$. This leaves $\mathbf{2}$ choices for $2,4$.