How can I figure out who can give gifts to whom on Christmas?

Question

Let's suppose there is a family of seven people, say,

["John", "James", "Jenna", "Joseph", "Jane", "Jacob", "Joanne"]

they are all getting prepared for the christmas gift giving season. They have agreed upon some rules to make sure everything will work smoothly:

• Everybody must give one gift.
• Everybody must receive one gift.
• Nobody may give a gift to himself.
• Nobody may give a gift to his spouse. (Jane and John are spouses)
• Nobody may give to the same person he gave to last year. (Last year, John gave to James, James gave to Jenna, Jenna gave to Joseph, Joseph gave to Jane, Jane gave to Jacob, Jacob gave to Joanne, and Joanne gave to John)
• Finally, no two people may give a gift to each other. For example, if John is giving to Jenna, Jenna may not give back to John.

With the rules as complicated as they are, it was hard for them to figure out who can give to whom while still abiding by these rules. Consequently, they have hired me to write a program that will display all of the possible legal ways people can give to each other.

What algorithms could I use to solve this problem elegantly?

Answer 1

I would use a simple backtracking algorithm. Using a Python generator function:

def calc_gifts(names, blacklist, gifts={}):
    if len(names) > 0:
        name, rest = names[0], names[1:]
        for other in names + list(gifts):
            if (other != name and 
                    other not in blacklist[name] and
                    (other not in gifts or gifts[other] != name) and
                    other not in gifts.values()):

                gifts_new = dict(gifts.items() + [(name, other)])
                for solution in calc_gifts(rest, blacklist, gifts_new):
                    yield solution
    else:
        yield gifts

Now, we set up the names and blacklists and have the generator generate a solution:

all_names = ["john", "james", "jenna", "joseph", "jane", "jacob", "joanne"]
blacklist = {"john":   ["james", "jane"],
             "james":  ["jenna"],
             "jenna":  ["joseph"],
             "joseph": ["jane"],
             "jane":   ["jacob", "john"],
             "jacob":  ["joanne"],
             "joanne": ["john"]}
generator = calc_gifts(all_names, blacklist)
solution = next(generator)

solution then is a dict of gift-givers and -receivers, e.g. {'joanne': 'joseph', 'james': 'john', 'jane': 'joanne', 'joseph': 'jacob', 'jacob': 'jane', 'john': 'jenna', 'jenna': 'james'}.

For the first solution, i.e. using next(generator), calc_gifts is invoked just 10 times; for all 224 solutions, e.g. using list(generator) it is invoked approx. 1000 times.

Answer 2

What if you were to start with a 7x7 grid, with a row and a column for each person, indicating if the person mentioned in the row is allowed to give a gift to the person mentioned in the column.

Initially, mark every combination as allowed, and then start removing the ones that are explicitly disallowed by your constraints 3, 4 and 5. Every valid combination of gifts must be a subset of the ones you have left at this point. This will be your starting position.

Now you have to start making decisions, and every decision will affect the possibilities you have left. Some decisions may turn out to be the wrong, causing not everyone to get a gift in the end. In that case, you should take back that decision and try another instead (hint: use recursion for this).

If you try all possibilities in a structured manner, you are bound to find all solutions if they exist.

Now, make it their money's worth :)