[HN Gopher] How to solve the Secret Santa Problem using graph th...
___________________________________________________________________
How to solve the Secret Santa Problem using graph theory
Author : fck_r_sns
Score : 53 points
Date : 2021-02-08 12:50 UTC (1 days ago)
(HTM) web link (medium.com)
(TXT) w3m dump (medium.com)
| dom111 wrote:
| 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
| selwtysaxoac wrote:
| 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.
| adamc wrote:
| Did you read the article? It adds constraints.
| selwtysaxoac wrote:
| Yes, I asked about the unconstrained problem. Sorry, I should
| have mentioned that.
| cochne wrote:
| 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)
| rflrob wrote:
| I think it can as well, unless you require constraints as in
| the article.
| jeromegv wrote:
| 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.
| anonjustice wrote:
| What a waste of brainpower. Better off spending time solving
| serious problems. https://80000hours.org/
| rflrob wrote:
| 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.
| Znafon wrote:
| 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...
| taldo wrote:
| 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.
| LeifCarrotson wrote:
| 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.
| dmurray wrote:
| 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?
| jgalt212 wrote:
| Video on this by the charming Dr Hannah Fry
|
| https://www.youtube.com/watch?v=5kC5k5QBqcc
| klodolph wrote:
| 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.
| kevincox wrote:
| I did a ruby script that sent emails. It also would restart if
| some constraints were failed.
| apronchenkov wrote:
| 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
| zaik wrote:
| 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.
| Uehreka wrote:
| 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.
| jstanley wrote:
| 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.
| ReaLNero wrote:
| 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?
| jbarberu wrote:
| 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).
| antihero wrote:
| 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.
___________________________________________________________________
(page generated 2021-02-09 23:02 UTC)