Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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)?
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.
