CODEWITHSUNDEEP
algorithmcombinations
Torque
Torque

Reputation: 19

Ways to get combination from set of sets

I have a set of sets with possible repeats across sets, say {{1, 2, 3, 7}, {1, 2, 4, 5}, {1, 3, 5, 6}, {4, 5, 6}}. I want to know if I can get a specific combination, say {1, 2, 3, 4} by choosing one element from each set, and if so, I want to know how many ways I can do this.

I can do this via bruteforcing (finding all ways to get the first element, then ways to get the second element, and so on), but this seems rather painful and inefficient. Is there a better way to go about this?

Upvotes: 1

Views: 185

Answers (1)

Unlikus
Unlikus

Reputation: 1858

You can reduce your problem to maximum bipartite matching (It is equivalent actually).

One the left side you have all the elements of your set. On the right side you have all your sets. You connect a number of your left side with a set on the right iff the number is contained in the set.

Now you can now apply an algorithm like Hopcroft-Karp https://de.wikipedia.org/wiki/Algorithmus_von_Hopcroft_und_Karp to find the maximal matching. If it is as big as your set you have an assignment as you requested, otherwise not.

The number of optimal matchings is NP-hard, see https://www.sciencedirect.com/science/article/pii/S0012365X03002048 : But the enumeration problem for perfect matchings in general graphs (even in bipartite graphs) is NP-hard

Upvotes: 1

Related Questions