patternMinor
Constructing a random Hamiltonian Cycle (Secret Santa)
Viewed 0 times
randomcyclehamiltonianconstructingsecretsanta
Problem
I was programming a little Secret Santa tool for my extended family's gift exchange. We had a few constraints:
So at this point, I think what I'm looking at is a directed graph, and I want to find a random Eulerian Hamiltonian Cycle.
Naively, I would say:
But this doesn't give all permutations equal weight. Flipping a coin to choose the first neighbour could greatly limit subsequent possibilities, like in the graph below:
If in the example above I start with A, I could choose B or C at 50% probability each.
So with my naive approach, I would choose cycle 1 50% of the time, and 2 and 3 25% of the time each.
The route I ended up taking this year was to shuffle all of the vertices, and then check if it was in fact an admissable cycle. But this gets less efficient as there are more constraints.
Is there an efficient way to generate a random Hamiltonian Cycle where each cycle has equal probability?
Edit:
By "efficient" I mean more efficient in runtime and/or space than generating the set of every Hamiltonian Cycle, and then choosing one at random.
- No recipients within the immediate family
- Nobody should get who they got last year
- The whole thing should be a cycle (Sandy gives to George, George to Tom, Tom to Susan, Susan back to Sandy)
So at this point, I think what I'm looking at is a directed graph, and I want to find a random Eulerian Hamiltonian Cycle.
Naively, I would say:
- Start with a random vertex
- Randomly choose a neighbour that hasn't been hit yet
- Recurse until you reach a cycle (solution) or find a node with no neighbours (backtrack and choose a different random neighbour)
But this doesn't give all permutations equal weight. Flipping a coin to choose the first neighbour could greatly limit subsequent possibilities, like in the graph below:
A -> [B, C]
B -> [C, D, E]
C -> [A, D, E]
D -> [A, B, E]
E -> [A, B]If in the example above I start with A, I could choose B or C at 50% probability each.
- If I choose B, the only cycle is 1)
A->B->C->D->E->A
- If I choose C, there are multiple paths: 2)
A->C->D->B->E->A, 3)A->C->E->B->D->A
So with my naive approach, I would choose cycle 1 50% of the time, and 2 and 3 25% of the time each.
The route I ended up taking this year was to shuffle all of the vertices, and then check if it was in fact an admissable cycle. But this gets less efficient as there are more constraints.
Is there an efficient way to generate a random Hamiltonian Cycle where each cycle has equal probability?
Edit:
By "efficient" I mean more efficient in runtime and/or space than generating the set of every Hamiltonian Cycle, and then choosing one at random.
Solution
I'm not sure what you mean by an efficient algorithm, but the problem of finding any Hamiltonian path is NP-complete, which means that it is very unlikely that a polynomial time algorithm exists for your problem.
If the number of people $n$ is small, say less than 10, then it is feasible to solve the problem by brute force. Generate all $n!$ permutations of the people. Remove all permutations from the list that do not form a Hamiltonian cycle and do not satisfy your additional constraints. The time and space complexity is $O(n! n)$. Then pick a random permutation from the list.
If the number of people $n$ is small, say less than 10, then it is feasible to solve the problem by brute force. Generate all $n!$ permutations of the people. Remove all permutations from the list that do not form a Hamiltonian cycle and do not satisfy your additional constraints. The time and space complexity is $O(n! n)$. Then pick a random permutation from the list.
Context
StackExchange Computer Science Q#33839, answer score: 4
Revisions (0)
No revisions yet.