1
$\begingroup$

Let's say I have a list of "Items"

I also have a list of "Bags". Each bag is a set of "Items" which gives what item can be placed in that bag. But only one item can go in each bag.

I want to place all items in a bag. It's okay if there are empty bags left over.

Does this sort of problem have a name and a solution other than a naive depth first search (a link in the direction of such an approach will be fine)?

$\endgroup$

1 Answer 1

1
$\begingroup$

This problem is call "$X$-satuated bipartite matching" or Hall's marriage problem, which is discussed at here on Wikipedia.

Consider each item as a woman. Each bag is a man. If item $a$ is allowed to be placed in bag $x$, it means woman $a$ and man $x$ can be married happily. Only one item can go in each bag corresponds to the assumption of monogamy, a man with one wife and a woman with one husband. So the problem is asking whether it is possible that all women can be married happily.

Please check the link for details and much more interesting result around. You can find various efficient algorithms to solve the problem and related problems.

Since we are here, we should mention the following celebrated theorem.

Hall's Marriage Theorem — A family $S$ of finite sets has a transversal if and only if $S$ satisfies the marriage condition.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.