Consider we have set S:
S = {1,2,3,4,5,6}
and 3 (say k) subsets of S:
S_1 = {1,2,3}
S_2 = {2,3,4,5}
S_3 = {1,3,6}
What is the total number of cases choosing one element from each subsets?
Same element cannot picked from different subset, and the order is not considered.
For example,
S_1 = {2}, S_2 = {3}, S_3 = {6}
and
S_1' = {3}, S_2' = {2}, S_3' = {6}
considered as same. And
S_1' = {3}, S_2' = {3}, S_3' = {1}
is invalid since S_1' and S_2' choose the same element.
How can I formulate this?
This problem is similar to counting the number of perfect matchings in a bipartite graph.
To model it this way, construct a bipartite graph where A = { 1, ..., k }, B is the original set S, and an edge from x ∈ A to y ∈ B exists when y is a member of the set S_x.
A perfect matching corresponds with a subset of the edges matching every element of A to a distinct element of B; for each set S_x this matching selects a distinct element y ∈ S_x. That said, multiple distinct matchings may match the same k elements from B, which means this overcounts due to order not being considered in your problem (i.e. for your purpose, it doesn't matter which edges map from A to those k elements). Nonetheless, the problems are quite similar and it's likely that each can be reduced to the other.
According to this answer on math.SE there is no known efficient algorithm for counting perfect matchings, so there is probably no known efficient algorithm for this similar problem, either. That suggests you're unlikely to do much better than a backtracking search of some sort.