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.



Generating sets of tuples from possible candidate lists (or finding perfect matchings in uniform hypergraphs)
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$. 


