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:
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?
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.
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 :)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With