5

我正在寻找一种算法，给定一组数字 {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 个数字相邻。

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

4

3 回答 3

1

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

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

于 2012-05-09T03:25:29.300 回答
1

基本上你想知道你是否可以创建数字链。将每个数字放入一个跟踪该数字和最多两个邻居的链中。使用规则将链连接在一起。当您加入两条链时，您最终会得到一条带有两个松散端（邻居）的链。如果你能通过所有规则而不用完松散的结局，那么它就可以工作。

于 2012-05-09T00:56:30.667 回答
0

我已经实现了图形解决方案，并稍作修改。

如果一个节点有太多的邻居，该算法将删除一条边并再次检查图。然后我使用回溯回滚并检查是否可以丢弃下一个边缘......这种方法与我编写的蛮力方法给出相同的结果。

就复杂性而言，这个解决方案似乎比蛮力更好，尽管我不能在超过 20 个数字上运行它（蛮力只有 8 个）。从某种意义上说，这是合乎逻辑的，因为这样的图实际上可以一次生成一个有效排列的子集，而且在最坏的情况下，它相当于在一组边上找到一些组合。毕竟是回溯。

鉴于旋转对排列的有效性没有任何影响，我正在考虑将 a0 固定在第一个位置（这可以通过简单地旋转一个有效的排列直到 a0 处于第一个位置来实现）然后尝试构建从那里的解决方案。

使用 DP，我可能会得到比指数复杂度更好的东西。但我必须说我仍然不确定从哪里开始:)

于 2012-05-09T16:53:32.480 回答