Inspired by this StackOverflow question, I am wondering if there is an efficient algorithm for the following problem:
Assume $n$ items and $n$ boxes, with all boxes numbered numerically and all items labelled alphabetically. Each item has a disallow list: there are certain boxes that item cannot be put into. Generate a mapping of items to boxes that does not violate any item's disallow list.
For bonus points, I would be interested in being able to generate all such mappings.
At first blush, the problem appears to be the inverse of the stable marriage problem, in that everyone has a strict list (rather than an ordinal ranking) of whom they don't want to get married to but will settle for anyone else (and strictly speaking the men/boxes have no preferences). Edit: it appears this problem is closer to bipartite matching.
A very naive solution is to simply generate all permutations and check which ones don't violate any disallow lists, but this grows as $O(n!)$. Are there any polynomial time solutions out there?