c++ - 枚举完整图的哈密顿循环的算法(循环、反向、环绕或重复的排列不计算在内)

Question

我想生成一个完整的无向图的所有哈密顿循环(一个集合的排列，其中循环和反转被视为重复，并被排除在外)。

例如，{1,2,3}的排列是

标准排列:

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

我希望程序/算法为我打印什么:

1,2,3

因为 321 只是 123 向后，所以 312 只是 123 旋转一位，等等。

我看到很多关于给定集合具有这些循环的数量的讨论，以及查找图是否具有哈密顿循环的算法，但没有关于如何在完整的无向图中枚举它们的讨论(即可以在集合中的任何其他数字之前或之后的一组数字。

我非常想要一个算法或 C++ 代码来完成这项任务，或者您是否可以指导我找到与该主题相关的资料。谢谢!

Answer 1

您可以对输出设置一些限制以消除不需要的排列。假设我们想要排列数字 1，...，N。为避免某些特殊情况，假设 N > 2。

为了消除简单的旋转，我们可以要求第一位是 1。这是真的，因为任意排列总是可以旋转成这种形式。

为了消除反转，我们可以要求第二位的数字必须小于最后一位的数字。确实如此，因为从 1 开始的两个互为逆序的排列中，正好有一个具有这个性质。

因此，一个非常简单的算法可以枚举所有排列并排除无效的排列。当然还有优化的可能。例如，在生成步骤中可以很容易地避免不以 1 开头的排列。