javascript - 推断组序列的算法名称

Question

我有一个像这样的数组:

var groups = [
  ['one', 'three', 'four'],
  ['two', 'three', 'six', 'seven'],
  ['three', 'four', 'five'],
]

由此我需要根据给定的顺序推断出适当的值序列(为了简单的例子，我给出了数字)。换句话说，由于每个数组都有缺失数据，因此需要引用其他数组来获得所有组的最优序列。理想输出:

['one', 'two', 'three', 'four', 'five', 'six', 'seven'];

我可以写这个，但我完全确定这是一个非常常见的算法。我只是不知道它的名字。有什么想法(或解决它的简单方法)吗？

Answer 1

一种可能的方法是使用 topological sorting在有向无环图中找到最短路径:

1. 为每个唯一的“单词”定义一个节点
2. 定义一组相邻“词”之间的有向边，从左(源)到右(汇)
3. 将每条边的权重计算为某个函数，该函数测量一组中两个词彼此相邻的次数(需要在这里进行实验)
4. 计算 topological orderings 的集合构建的 DAG。
5. 计算shortest path在 DAG 中。

生成的路径就是您的解决方案。请注意，您必须确保您的组定义了一个非循环图。