Constructing a random Hamiltonian Cycle (Secret Santa)

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

Observations:

Consider the trivially simple ConstraintMap:

constraints =  fromList [ ("a", ["b","d"])
                        , ("b", ["a","c","d"])
                        , ("c", ["a"])
                        , ("d", ["b","c"])
                        ]

There are only two Hamiltonian cycles satisfying the ConstraintMap:

"c" -> "a"     "c" -> "a"
 ^      |  and  ^      |
 |      v       |      v
"d" <- "b"     "b" <- "d"

There are $4! = 24$ permutations but only $2$ are valid Hamiltonian cycle solutions. Therefore we should devise an algorithm which only uses the significantly smaller search space of valid Hamiltonian cycles!

We can do this by viewing all the possible constructions as a tree

We select an arbitrary element as the root node (WLOG "a"). Then the branches of this element are it's recipients elements, minus any recipient element in it's parental line. We apply this structure recursively to depth $d = length(\;constraints\;)$ to construct all valid Hamiltonian cycles.

        "a"
      /     \
   "b"       "d"   -- Note no "a" in "b"'s children because "a" is "b"'s parent
  / | \     /   \  -- The same rules of excluding the parental line follows for all nodes!
"c" X "d" "c"   "b"
 |   / |   |   / | \
 X  X "c"  X  X "c" X
       ^         ^
       +---------+--- Valid terminal nodes because "c" maps to "a"

As you can see, we have in fact constructed all $2$ valid Hamiltonian cycles:

        "a"
      /     \
   "b"       "d"
      \         \ 
      "d"       "b"
       |         | 
      "c"       "c"

We can select a single uniformly random valid Hamiltonian cycle by preforming a depth limited search over a uniformly randomized search space. We do this in a manor similar to the tree construction above.

Algorithm:

• We first fix an arbitrary element as the root node.
• We then populate the branches of this element with the possible recipients elements, minus any recipient element in it's parental line.
• We then randomly permute the branches of the element and begin a depth limited search on the first element in the permutation.
• We apply this recursively to depth $d = length(\;constraints\;)$.
• We return the first path of depth $d$ which satisfies the Hamiltonian constraints.

This runs in $\mathcal{O}(n)$ memory and $\Omega(n)$ & $\mathcal{O}(n!)$ time.

Best Case Complexity:

• Linear time to generate a valid solution in the first few attempts

Worst Case Complexity:

• Factorial time to generate all possible solutions and determine none satisfy constraints

Average Case Complexity:

• I don't know, but for my test battery of real world familial constraints with arrangement histories my Haskell implementation returns a valid cycle instantaneously ($time\;<\;\frac{1}{20}\;sec$).

Implementation:

My Haskell implementation is viewable here:

Imperative Pseudocode:

List<String> selectCyclicArrangement(Map<String,Set<String>> constraints) {
  root = chooseRandom(keys(constraints));
  height = length(constraints);
  return lazySelectArrangement( root
                              , height
                              , constraints
                              , constraints
                              , 1
                              , root);
}

List<String>? lazySelectArrangement(String root
                                    , int height
                                    , Map<String, Set<String>> originalConstraints
                                    , Map<String, Set<String>> constraints
                                    , int depth
                                    , String key) {
  if(depth == height) {
    if(originalConstraints[key].contains(root))
      return (new List<String>()).add(key);
    else
      return null;
  }
  branches = constraints[key];
  randomlyPermute(branches);
  if(branches.length == 0)
    return null;
  reducedConstraints = constraints.removeFromAll(key);
  result = null
  foreach(branch in branches) {
    result = lazySelectArrangement( root
                                  , height
                                  , originalConstraints
                                  , reducedConstraints
                                  , depth+1
                                  , branch);
    if(result != null)
      break;
  }
  if(result != null)
    return result.add(key);
  else
    return null;
}