I am given $n$ sets with a selection of $m$ elements, such as:
$$S = \{\{0\}, \{1, 2, 3\}, \{1, 2, 3\}, \{3\}\}$$
I am trying to calculate the number of unique sequences that contain all elements that can be generated. For the case above the answer would be $2$:
$$s_0 = (0, 1, 2, 3)$$ $$s_1 = (0, 2, 1, 3)$$
I've been working with the cartesian product, filtering out the sets that did not meet the requirements. However, the computational cost is too high. Other ideas that got me nowhere were reducing by intersection, translating into a binary matrix…
Is there a way I could operate the subsets to find out how many unique sequences can be formed? Thanks!
For clarity, a couple examples more:
$S = \{\{0\}, \{1\}, \{2\}, \{3\}\}$: $s_0 = (0, 1, 2, 3)$
$S = \{\{0\}, \{1\}, \{1, 2, 3\}, \{1, 2, 3\}\}$: $s_0 = (0, 1, 2, 3)$, $s_1 = (0, 1, 3, 2)$
The size of the problem is roughly $n = 100; m = [0..5000]$
This is sometimes called the marriage problem, or the matching problem.
It is often written as a question about bipartite graphs. Consider a bipartite graph $G$ with $n$ nodes $x_1,\dot,x_n$ in one part and $m$ nodes $y_1,\dots,y_m$ in the second parts. We consider the set $S_i$ to be the set of all $y_i$ such that $(x_i,y_j)\in G$.
You are trying to find the number of edge matchings of size $n$.
The wikipedia page on matchings is a little vague. Whether there is such a mapping can be deduced in polynomial time, but the question of the counting question is unfortunately badly explained. The page states the counting problem is #P-complete, but it doesn't say whether that is for the general case, or if the bipartite case is also #P-complete. I believe it means that the bipartite case is #P-complete, but I'm not sure. I've added a question to the "Talk" section for that page asking for clarification.
If the bipartite case is still #P-complete, that means it is highly unlikely you will find a polynomial-time algorithm to count.
If you happen to have more structure or knowledge about these sets/this graph, then you might be able to come up with an algorithm that uses the answer, or one that estimates the answer reasonably well in most cases.