Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How to solve the Secret Santa Problem using graph theory

medium.com

Post reply on HN
Print view View original

21–25 of 25 posts

Re: How to solve the Secret Santa Problem using graph theory

#21

Post by antihero »

jbarberu wrote: post #20

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.

Re: How to solve the Secret Santa Problem using graph theory

#22

Post by dom111 »

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

Re: How to solve the Secret Santa Problem using graph theory

#23

Post by zaik »

apronchenkov wrote: post #7

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.

Re: How to solve the Secret Santa Problem using graph theory

#24

Post by kevincox »

klodolph wrote: post #19

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.

Re: How to solve the Secret Santa Problem using graph theory

#25

Post by teawrecks »

Uehreka wrote: post #8

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 would argue that allowing multiple cycles is superior because it dramatically increases the possible number of cases you're randomly choosing from.
Post reply on HN