[Solved]: Constructing a random Hamiltonian Cycle (Secret Santa)

ignougroup
Problem Detail: I was programming a little Secret Santa tool for my extended family’s gift exchange. We had a few constraints:

  • 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.

Asked By : Mark Peters

Answered By : Juho

You can do slightly better on space by using reservoir sampling. The overall approach we take is the same as suggested by @jnalanko, and it only works well for small enough $n$. We generate each permutation of ${1,ldots,n}$, but only keep one solution $X$ stored. At the end, $X$ will satisfy the property of being sampled uniformly at random from the set of all solutions. This is fairly straightforward to show by induction. This is easy to describe in pseudocode:

S := {1,...,n} i := 1 X := {} while(not visited each permutation of S)   if S is a valid solution     set X to S with probability 1/i     i := i + 1   S := next permutation of S

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33839

Leave a Reply