11–20 of 25 posts
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.
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.
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,…
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…
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.
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,…
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)