How to solve the Secret Santa Problem using graph theory | Hacker News Reader

How to solve the Secret Santa Problem using graph theory

medium.com

64 pointsfck_r_sns23 comments

Every 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.

Why is it a problem if there is more than one cycle? Surely it would be more of a problem if you knew everyone was in a single cycle because then you'd have more information about which assignments can't exist.

What if you could show people the secret santa graph with names removed, then they could modify it to look more fun, and then show the assignments?

I would argue that allowing multiple cycles is superior because it dramatically increases the possible number of cases you're randomly choosing from.

One year my family did this when we were on vacation in a foreign country. I happened to have my laptop with me and wrote a shell script that would generate a random Secret Santa graph. Each family member would go up to my laptop, it would say, “Are you Alice?” they’d press enter, and the program would say, “You are assigned to Bob. Press enter.” They’d press enter and it would clear, ready for the next person.

I did a ruby script that sent emails. It also would restart if some constraints were failed.

When we did secret Santa a few years back I wrote a little python script similar to the below:

    import random
    l = ['Alice', 'Bob', 'Benny', 'Dolores']
    random.shuffle(l)
    r = dict(zip(l, (l[(i + 1) % len(l)] for i in range(0, len(l)))))
    print(r)

Basically just shuffle the list, assign everybody the one next on the list (with wrap around).

This is exactly what I did when I wrote an assassins game for a project at uni. Gets interesting when you try and branch out and have many-many targets/assassins.

Video on this by the charming Dr Hannah Fry

https://www.youtube.com/watch?v=5kC5k5QBqcc

I 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.

[1] https://mathworld.wolfram.com/HamiltonianPath.html

Just deciding the question "Is there a Hamiltonian cycle in this graph?" is already NP complete. The author suggests the problem is easier than TSP because he "just" has to find any hamiltonian path, but the problem is just as hard. If I remember correctly, one can build a graph from any given 3SAT problem instance in polynomial time where: Satisfiable <=> Existence of a hamiltonian cycle.

Can'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.

Yes, I asked about the unconstrained problem. Sorry, I should have mentioned that.

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)

I think it can as well, unless you require constraints as in the article.

Clearly this is a fun problem! I did this a few years ago too[1] and thought it might be a useful service, I made a naive solution in JS for my needs that takes a Boolean matrix specifying who can't give to another! I even made a code golf challenge for it!

[1]: https://gist.github.com/dom111/4a4ede77f44c46c5d968

What 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.

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?

As in many holiday events, it's just tradition that requires a Hamiltonian cycle. And tradition is not known for its reasonableness or flexibility!

The tradition says that after opening the gift they've received, they have to wear the funny Santa hat and bring the gift they brought to the person they were randomly assigned.

If the graph is not Hamiltonian, and instead goes A-B-C-A and D-E-F-D and G-H-G, there are going to be several awkward moments where someone has to arbitrarily choose someone who hasn't gone yet. It's really easy to generate these loops, and hard to get a 'proper' graph by drawing randomly from a hat, especially if you add other constraints like excluding spouses and your own kids/parents.

Maybe 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.

The Fisher-Yates algorithm has O(n) running time but it is slightly different than what the author suggested, instead of removing the element from the array, you swap it with the last, that way you are sure not to get it again by simply reducing the upper bound of your random function and it's a O(1) operation so the total running time is O(n): https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#T...

Fascinating, I assume I could use some thing like that to guess the secret Santa. Knowing I cannot have my wife and might know a few of who got who within the group, I could have a list of "likely" possibilities.

Reply on news.ycombinator.com