algorithm - 给定一组数字和元素相对位置的一些条件，生成一组排列

Question

我正在寻找一种算法，给定一组数字 {0, 1, 2, 4, 5...} 和一组关于每个元素相对位置的条件，将检查是否存在有效排列.条件始终为“原始数组中位置 i 中的元素必须是位置 j 或 z 中的元素的下一个(相邻)”类型。
排列中的最后一个和第一个元素被认为是相邻的。

这是一个简单的例子:

设数字为 {0, 1, 2, 3}
和一组条件:a0 必须紧挨着 a1，a0 必须紧挨着 a2，a3 必须紧挨着 a1
此示例的有效解决方案是 {0,1,3,2}。

请注意，此解的任何旋转/对称也是有效解。我只需要证明这样的解决方案存在。

另一个使用相同集合的例子:
a0 必须在 a1 旁边，a0 必须在 a3 旁边，a0 必须在 a2 旁边。

这个例子没有有效的解决方案，因为一个数字只能与 2 个数字相邻。

我现在唯一能想到的就是使用某种回溯。
如果存在解决方案，这应该会快速收敛。如果不存在解决方案，我无法想象有什么方法可以避免检查所有可能的排列。正如我已经说过的，旋转或对称性不会影响给定排列的结果，因此应该可以减少可能性的数量。

Answer 1

将其表述为图形问题。连接每对需要彼此相邻的数字。你最终会得到一堆连接的组件。每个组件都有许多排列(我们称它们为迷你排列)，您可以对组件进行排列。

当您创建图形时，请确保每个组件都遵循一系列规则:没有循环、没有超过两个顶点的顶点等。