Algorithm for Enumerating Hamiltonian Cycles of a Complete Graph (Permutations where loops, reverses, wrap-arounds or repeats don't count)

Question

I want to generate all the Hamiltonian Cycles of a complete undirected graph (permutations of a set where loops and reverses count as duplicates, and are left out).

For example, permutations of {1,2,3} are

Standard Permutations:

1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1

What I want the program/algorithm to print for me:

1,2,3

Since 321 is just 123 backward, 312 is just 123 rotated one place, etc.

I see a lot of discussion on the number of these cycles a given set has, and algorithms to find if a graph has a Hamiltonian cycle or not, but nothing on how to enumerate them in a complete, undirected graph (i.e. a set of numbers that can be preceded or succeeded by any other number in the set).

I would really like an algorithm or C++ code to accomplish this task, or if you could direct me to where there is material on the topic. Thanks!

Answer 1

You can place some restrictions on the output to eliminate the unwanted permutations. Lets say we want to permute the numbers 1, ..., N. To avoid some special cases assume that N > 2.

To eliminate simple rotations we can require that the first place is 1. This is true, because an arbitrary permutation can always be rotated into this form.

To eliminate reverses we can require that the number at the second place must be smaller than the number at the last place. This is true, because from the two permutations starting with 1 that are reverses of each other, exactly one has this property.

So a very simple algorithm could enumerate all permutations and leave out the invalid ones. Of course there are optimisations possible. For example permutations that do not start with 1 can easily be avoided during the generation step.

Answer 2

An uber-lazy way to check if a path is the same one that starts in a different point in the cycle (IE, the same loop or the reverse of the same loop is this:

1: Decide that by convention all cycles will start from the lowest vertex number and continue in the direction of the lower of the two adjacent ordinals.

Hence, all of the above paths would be described in the same way.

The second, other useful bit of information here:

If you would like to check that two paths are the same you can concatenate one with its self and check if it contains either the second path or the reverse of the second path.

That is,

1 2 3 1 2 3 

contains all of the above paths or their reverses. Since the process of finding all hamiltonian cycles seems much, much slower than the slight inefficiency this algorithm has, I felt I could throw it in :)