Algorithm for picking items from sets

Question

I have a collection of sets S[i], I need to pick C[i] items from each correspoinding set. Some items might belong to several sets at once, picking the same item twice is not allowed.

Here's an example to explain better:

Set #1 [b, c, d, e], pick 2
Set #2 [a, b, c], pick 2
Set #3 [w, x, y, z], pick 1
Set #4 [a, d, e], pick 1

One of the solutions would be:

Set #1 [b, d]
Set #2 [a, c]
Set #3 [x]
Set #4 [e]

I don't need to find all possible solutions, just any one that satisfies the conditions above.

My question is: is there a better approach other than bruteforcing all possible combinations until I find one? Obviously, greedy algorithm won't work (picking [b, c] for set #1 will make it impossible to pick 2 items from set #2). Do any other options exist? Is my problem equivalent to some well-known problem?

If brute force is the only option, what's the best way to implement it to avoid going down dead-ends? E.g. if I pick:

Set #1 [b, e]
Set #2 [a, d]

it would be useless to try all possible combinations for set #3 since picking anyting from set #4 is already impossible.

• Shrey Joshi: recursion + backtracking could work. As in, recursively try going over all the combinations, and at each step, check to see if a solution is possible. If it's not, then go back one step and continue with the next combination.
• torvin: That's basically brute force, right? I wonder if there are better ways
• n. m. could be an AI: Looks like generalised bipartite matching as described here simons.berkeley.edu/sites/default/files/docs/831/… where sets and elements are the partitions.
• kaya3: Yes, this can be made into a straightforward bipartite matching problem by just duplicating the sets which you have to pick two from.
• torvin: @n.'pronouns'm. Why don't you post an answer so I can accept it? sounds like I can use this? en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm

Answer 1

This can be modelled as a bipartite matching problem: the nodes on the left are the individual elements (a, b, c...) and the nodes on the right are the sets to be chosen from, with multiple nodes representing each set which should be chosen from multiple times. An edge exists from an element (on the left) to a set (on the right) if that element is a member of that set.

The goal is then to compute a matching (i.e. a set of independent edges) which includes every node on the right; this would necessarily be a maximum cardinality matching, so you can use any algorithm for maximum cardinality bipartite matching. There are several which run in low-degree polynomial time, so these will beat backtracking search for large inputs. (Technically this will be pseudopolynomial, because the transformation to a bipartite graph involves duplicating the sets which should be chosen from multiple times; but the same issue will likely affect backtracking searches.)

• torvin: Thank you, I tried using Edmonds–Karp algorithm and it works! What if I also have a weight assigned to each element of the set (i.e. vertex on the left) and I want to minimise or maximise the total weight?
• kaya3: Wikipedia should also have a page or section about maximum weight matching; for minimising, you can transform the weights to convert it to a maximisation problem.
• torvin: Thank you! I ended up using Hungarian algorithm with Edmonds–Karp inside for "find the minimum number of lines to cover zeroes" step (by turning zeroes into edges for E-K to find the matching). Worked perfectly for my case