python - 如何按规则排序但有重复项解决循环引用？

Question

为了更清楚地解释我的问题，我将从解释我面临的真实案例开始。

我正在构建一个物理面板，上面有许多可以选择性点亮的单词，以便组成句子。这是我的情况:

1. 我知道我要显示的所有句子
2. 我想找出[其中之一] 最短的 ORDERED 单词集，使我能够显示所有句子

例子:

 SENTENCES:
 "A dog is on the table"
 "A cat is on the table"
 SOLUTIONS:
 "A dog cat is on the table"
 "A cat dog is on the table"

我试图通过“位置规则”来解决这个问题，在所有句子中使用的所有单词的集合中找到每个唯一的单词，哪些单词应该在它的左边或右边。在上面的例子中，“on”这个词的规则集是“left(A, dog, cat, is) + right(the, table)”。

这种方法适用于微不足道的情况，但我的现实生活中有两个额外的困难让我陷入困境，而这两个困难都与重复单词的需要有关:

1. 句内重复:“the cat is on the table”有两个“the”。
2. 循环引用:在一组三个句子“A red cat”+“My cat is on the table”+“That table is red”中，规则规定 RED 应该位于CAT 的左边，CAT 应该在 TABLE 的左边，TABLE 应该在 RED 的左边。

因此我的问题是:

What is the class of algorithms (or even better: what is the specific algorithm) that studies and solves this kind of problems? Could you post some reference or a code example of it?

编辑:复杂程度

从第一轮的回答来看，实际的复杂程度(即句子之间的差异程度)似乎是一个重要因素。因此，这里有一些相关信息:

1. 我有大约 1500 个句子要表达。
2. 所有句子本质上都是对约 10 个句子的受限池的修改，其中只有几个词发生变化。基于前面的示例，这有点像我所有的句子都会谈到“某人的宠物相对于一件家具的位置”或“某人家具的物理描述”。
3. 用于构建所有句子的唯一单词数为 <100。
4. 句子最多 8 个词。

对于这个项目，我使用的是 python，但任何合理可读的语言(例如:未混淆的 perl!)都可以。

提前感谢您的宝贵时间!

Answer 1

如果我没理解错的话，这相当于 shortest common supersequence问题。这个问题是 NP 完全的，但存在近似算法。谷歌turns up a few papers , 包括 this one .

在两个输入序列的情况下，这个问题可以用简单的 DP 算法解决，但这并不能推广到多个序列，因为每个序列本质上都需要你向 DP 表添加一个维度，这会导致指数级的打击-向上。