字符串分组

Question

我有一个字符串列表的可能组列表。每个字符串由几个单词组成，这些单词是字符串元素。我想根据这些元素对字符串进行分组。

每个组都基于一个公共单词：组中的所有字符串都必须包含该单词——尽管我不要求所有包含该单词的字符串都在同一组中。包含N个单词的字符串可以属于N个不同的组中的任何一个。每个字符串只能在一个组中。每个组必须至少有两个字符串。

目标:形成组以最大化组中字符串的数量(最小化“孤立”字符串)。

例如，如果我有以下字符串列表：

cycle cost
pump cost
cycle analysis
cost example

我将每个字符串中所有可能的单词作为潜在的组。我现在想把这些字符串分组，这样所有的，或者尽可能多的，就可以组成一个组。

我尝试了一种天真的方法，首先采用字符串最多的组，在这个示例中，它将是cost，但这使得循环分析without a group。

我在这个例子中寻找的结果是:

cycle: cycle cost, cycle analysis
cost: pump cost, cost example

是否存在针对此类问题的算法？任何关于要采取的方法的指示都会有所帮助。

Answer 1

看起来@m69领先不错。你的问题有几处修改:

< li >取出尺寸为1的所有套件； < li >当一个集合被(暂时)添加到解决方案中时，该集合的所有元素必须从所有剩余集合中删除 < ul > <李>...任何少于两个元素的集合都会被删除。

不幸的是，这充其量是NP-hard。如果应用程序的输入不是大得离谱，我会使用带有自由回溯的强力试探法。

初始化：

< li >可行集合是指至少包含两个元素的集合。 < li >处理您的列表。 < ul > < li >将所有可行集合放入列表s。 < li >将所有元素放入宇宙u中。

过程：

< li >从S中选择一个集合P；将其添加到解决方案列表中。 < li >从s中的每个剩余集合中删除P的所有元素。 < li >从中删除所有不可用的器械包。 < li >如果S为空 < ul > < li >那么如果U的所有元素都存在于S中， < ul > < li >然后停止并报告解决方案。 < li >否则返回上一个呼叫级别

• 然后返回到上一个调用级别。
• 否则，请返回步骤 1，然后从 S 中选择下一组

您可以通过明智地对 S 中的集合进行排序来获得一些优势。我推荐一个贪婪的算法，其值根据其元素在S集中的可取性来测量。例如，仅出现在一个集合中的元素会将该集合推到列表的顶部。

这能让你开始吗？