search

jarhill0 / santa

Assign a secret santa over email
https://pypi.python.org/pypi/santa/
The Unlicense
5 stars 1 forks source link

Additional solving method: Maximum Bipartite Graph #5

Open trietvuive opened 2 years ago

trietvuive commented 2 years ago

You can construct a bipartite graph where both sides are the people involved in gift giving, remove all the restriction edges, and run an algorithm (either import it or write it yourself) to find the maximum matching in that graph. If the maximum matching contains all recipients, send the email, otherwise throw an error as no matching found.

This method would be more deterministic than random drawing and doesn't require setting a time limit, which might be a problem for large enough set of people.

jarhill0 commented 2 years ago

Thanks for the suggestion! I think that it would be a problem if the algorithm is indeed fairly deterministic. If the algorithm used randomness, though, then that would probably not be an issue.