6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In path (2) you wrote "E -> B" where "B -> E" was correct. $\endgroup$ – CR Drost Dec 4 '14 at 21:53
  • $\begingroup$ @ChrisDrost: Thanks, I'll correct that. I wrote a program to generate an example for me (and thus prove the premise to myself), and I copied the output wrong :). $\endgroup$ – Mark Peters Dec 4 '14 at 22:10
  • $\begingroup$ Hmmm... I asked a similar question on #haskell IRC last week... $\endgroup$ – recursion.ninja Dec 4 '14 at 23:20
  • $\begingroup$ The restriction to a Hamiltonian graph seems unnecessarily stringent. Surely A->B->C->A and D->E->F->D is a valid solution to a Secret Santa arrangement. $\endgroup$ – recursion.ninja Dec 4 '14 at 23:24
  • $\begingroup$ @recursion.ninja: You'd think so, but my family complained when it wasn't :). My family seems to insist on opening gifts such that the person who opened the last gift then gives their gift to their recipient. So having a lot of little cycles kills the buzz, and having one big cycle is the ideal. That said, I'm lucky enough to have a comparatively small extended family, so it's within reason to have this restriction. $\endgroup$ – Mark Peters Dec 4 '14 at 23:54
3
$\begingroup$

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
$\endgroup$
  • $\begingroup$ Smart...this seems like the perfect marriage between how I ended up doing it (which needed O(1) space, but could theoretically never terminate since it chooses its permutations randomly), and the approach that @jnalanko was suggesting. $\endgroup$ – Mark Peters Dec 4 '14 at 20:33
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the answer, I think your suggested approach validates and is similar to my approach of generating random permutations of people until I find an admissable one (differing in the worst case for runtime). By efficient, I think what I meant was "short of finding all Hamiltonian Cycles and then choosing one at random". I'll add that to the question. $\endgroup$ – Mark Peters Dec 4 '14 at 19:44
  • $\begingroup$ I suppose that in the worst case, there is no difference in complexity between generating every permutation and finding one permutation, is there? So maybe I'm fooling myself that there's anything to be saved by not having to find all permutations? $\endgroup$ – Mark Peters Dec 4 '14 at 19:52
  • $\begingroup$ @Juho: I'm happy with just one solution, but I want that one solution to be found with probability 1/n, where n is the total number of solutions. $\endgroup$ – Mark Peters Dec 4 '14 at 19:56
0
$\begingroup$

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;
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.