3 ms·
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 v
by taldo 6y ago
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.
- dmurray 6y agoRight, 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?
- LeifCarrotson 6y agoAs 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.