java - 合并订购 list

请允许我用一个例子来问这个问题:
假设我们有以下3个列表(为清楚起见，省略了双引号):

L1: (a, c, b, d, f, j)
L2: (b, e, j, k)
L3: (a, d, e, g, h, j, i)

输出列表可能类似于以下任何内容(还有更多解决方案)

Lanswer1: (a, c, b, d, e, f, g, h, j, i, k)
Lanswer2: (a, c, b, d, f, e, g, h, j, i, k)
Lanswer3: (a, c, b, d, e, f, g, h, j, k, i)

总而言之，生成的有序集

包含所有列表中的元素联合

保留所有原始列表中元素的顺序。

L4的第四个列表:(b，c，d)，当添加到输入中时，应引发异常(因为c在L1中位于b之前)

我通过检查得出了答案。有人可以建议一种算法来做到这一点吗？
谢谢-M.S.

最佳答案

这可以使用topological sorting完成。

首先从列表中构建有向图。列表的元素成为节点。边缘从第一个元素到第二个元素，从第二个元素到第三个元素，依此类推。

根据实现算法的方式，您可以获得所有可能的解决方案，也可能只有一个。同样，如果图形包含一个循环，则算法将因错误而停止。

这就是您列表中的图形的样子:

来源:

digraph {
  {
    edge [color = "red"]
    a -> c
    c -> b
    b -> d
    d -> f
    f -> j
  }
  {
    edge [color = "blue"]
    b -> e
    e -> j
    j -> k
  }
  {
    edge [color = "green"]
    a -> d
    d -> e
    e -> g
    g -> h
    h -> j
    j -> i
  }
}

关于java - 合并订购 list ，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5839108/