为了更清楚地解释我的问题,我将从解释我面临的现实案例开始。
我正在构建一个物理面板,上面有很多单词,可以选择性地点亮,以组成句子。这是我的情况:
- 我知道我想显示的所有句子
- 我想找出[one of] 最短的一组 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)。
这种方法适用于琐碎的案例,但我的现实生活中有两个额外的困难让我陷入困境,这两个都与重复单词的需要有关:
- 句子重复:“the cat is on the table”有两个“the”。
- 循环引用:在“一只红猫”+“我的猫在桌子上”+“那张桌子是红色的”三个句子中,规则规定 RED 应该在 CAT 的左侧,CAT 应该在TABLE 和 TABLE 的左侧应位于 RED 的左侧。
因此,我的问题是:
研究和解决这类问题的算法类别是什么(甚至更好:具体的算法是什么)?你能发布一些参考或代码示例吗?
编辑:复杂程度
从第一轮答案看来,实际的复杂程度(即一个句子与另一个句子有多大不同)是一个重要因素。所以,这里有一些信息:
- 我有大约 1500 个句子要表示。
- 所有句子本质上都是对大约 10 个句子的受限池的修改,其中只有几个单词发生了变化。在前面的例子的基础上,这有点像我所有的句子都会谈论“某人的宠物相对于一件家具的位置”或“某人的家具的物理描述”。
- 用于构建所有句子的唯一词数<100。
- 句子最多8个字。
对于这个项目,我使用的是 python,但任何合理可读的语言(例如:不是混淆的 perl!)都可以。
提前感谢您的宝贵时间!