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

Question

假设我们有以下列表:

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

我们想合并它们，以便尊重每个单独列表之间的顺序。上述问题的解决方案可能是 w, x, y, z, u。

如果我们有一个比较键(例如字符串比较；a < z)，这个问题就很容易了，因为这为我们提供了对组合列表中任何元素相对于其他元素的位置的引用。但是如果我们没有 key 呢？对于上述问题，我们可以将问题重述如下:

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图节点以获得满足所有约束的最终列表。

   如果您的图中曾经有一个循环，拓扑排序算法会检测到该循环，从而揭示您的原始列表引起的约束中的矛盾。