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