合并有序列表

Question

请允许我用一个例子来问这个问题:假设我们有以下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之前)

我通过检查得出了答案.任何人都可以建议一个算法来做到这一点？谢谢, - MS

Answer 1

这可以使用拓扑排序来完成.

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

根据您实施算法的方式,您可以获得所有可能的解决方案,或只获得一个.此外,如果图形包含一个循环,则算法将停止并出现错误.

这就是列表中的图形如下所示:

资源:

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
  }
}