我正在寻找一种算法,给定一组数字{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个数字相邻.
我现在能想出的唯一想法就是使用某种回溯方式.
如果存在解决方案,则应该快速收敛.如果没有解决方案,我无法想象有任何方法可以避免检查所有可能的排列.正如我已经说过的,旋转或对称不会影响给定排列的结果,因此应该可以减少可能性的数量.