合并排序的列表没有比较关键

Question

假设我们有以下列表：

list 1: x, y, z 
list 2: w, x 
list 3: u 

我们希望能够将它们合并使得每个个体之列的顺序得到尊重。针对上述问题的解决方案可能是w, x, y, z, u。

如果我们有一个比较关键字（例如字符串比较; < z），这个问题很容易，因为这给了我们对任何元素相对于组合列表中其他元素的位置的引用。但是我们没有钥匙的情况呢？对于上述问题，如下我们可以重述问题：

x < y AND y < z AND w < x where x, y, z, w, u are in {0, 1, 2, 3, 4} 

我目前解决这类问题的方法是将问题作为一个约束满足问题模型 - 我运行AC3弧一致性算法消除不一致的值，然后运行递归回溯算法来进行分配。这工作正常，但它似乎是矫枉过正。

是否有一个通用的算法或简单的方法来面对这种类型的问题？

Answer 1

1. 构建一个包含列表中每个字母的节点的图。

   x y z 
   
   
   w u 
   

2. 从字母X添加有向边缘字母Y的任何列表中每对连续的字母。

   x -> y -> z 
   ^ 
   | 
   w u 
   

3. Topologically sort图中的节点，以获得满足您的所有约束的最终名单。

   如果图中有一个循环，拓扑排序算法会检测到这个循环，揭示了原始列表引发的约束中的矛盾。