How to solve the Secret Santa Problem using graph theory
1–10 of 25 posts
Re: How to solve the Secret Santa Problem using graph theory
#2What I don't understand is why it has to be a hamiltonian cycle. It could be simplified to just picking the set of edges in the directed graph that make every vertex have one incoming and one outgoing edge. The naive approach would be to assign sequentially from a set of available receivers, such as people passing around a hat and picking numbers from it without replacement, and not having the last picked participant pick next.
Re: How to solve the Secret Santa Problem using graph theory
#3What I don't understand is why it has to be a hamiltonian cycle. It could be simplified to just picking the set of edges in the directed graph that make every vertex have one incoming and one outgoing edge. The naive approach would be to assign sequentially from a set of available receivers, such as people passing around a hat and picking numbers from it without replacement, and not having the last picked participant…
Right, it could be a set of disjoint cycles instead.
This constrains the problem less but I don't think it allows a simpler algorithm. Your approach still needs some backtracking, if I understand right: what if Alice and Bob are the last two to be picked?
Re: How to solve the Secret Santa Problem using graph theory
#4Video on this by the charming Dr Hannah Fry
Re: How to solve the Secret Santa Problem using graph theory
#5Can't the Secret Santa problem be solved just by shuffling an array of participants, and assigning a person A[i] to give a gift to a person A[(i+1)%N]?
I have a feeling that this is not correct, but cannot determine why.
Re: How to solve the Secret Santa Problem using graph theory
#6Maybe I’m not clever enough, but wouldn’t the naive implementation of the naive algorithm be O(n^2) operations? Depending on whether you have a linked list or an array, traversing to or removing a random element takes O(n) time, which you need to repeat n times.
Re: How to solve the Secret Santa Problem using graph theory
#7I recall that in a general case finding a hamiltonian cycle (or path) is already NP-complete. Although it should be a simple problem for small real graphs, what article suggests, I think, is to use a brute-force solution.
Re: How to solve the Secret Santa Problem using graph theory
#8Every year, when my extended family (13 cousins) does Secret Santa, I complain “There are likely multiple cyclic graphs in this space!” But rather than engage my criticism with the mathematical rigor it clearly deserves, they just choose to restart with a random cousin who hasn’t given a gift yet when they discover the cycle. This is clearly a sub-optimal solution, and I am glad that when the ritual recurs next year, I will have groundbreaking research to present to them to solve this conundrum once and for all!
In other news, at this past Secret Santa I got a desk-mounted boom for my Blue Yeti, which I use every day and am thankful for.
Re: How to solve the Secret Santa Problem using graph theory
#9Can't the Secret Santa problem be solved just by shuffling an array of participants, and assigning a person A[i] to give a gift to a person A[(i+1)%N]? I have a feeling that this is not correct, but cannot determine why.
Did you read the article? It adds constraints.
Re: How to solve the Secret Santa Problem using graph theory
#10Can't the Secret Santa problem be solved just by shuffling an array of participants, and assigning a person A[i] to give a gift to a person A[(i+1)%N]? I have a feeling that this is not correct, but cannot determine why.
This is true if there are no constraints, but the author mentions they introduce constraints like 'a person cannot give to their significant other' (or else it would be too hard to keep it a secret)