将集合合并为有向图

Question

我的输入是一组整数列表。意思是，每个集合都有一个我需要跟踪的索引。那些（唯一的）集合包含整数，不同的集合可以具有一个或多个共同的整数元素（也可能两个集合是相同的）。

我的目标是将这些集合不是作为一个列表来表示，而是作为一个树状结构，所以我可以消除多个集合共享的整数元素。该结构是具有人工根节点的有向图。其他节点是集合中的整数。根节点最多有n个孩子（n是组数）。这些孩子实际上是来自不同组的第一个整数，并且必须由该算法添加。有几个条件：

• 必须有可能通过树中的一个路径重新创建这样一个集合。
• 通过树的路径必须是无歧义的，没有顶点可以有多个孩子。
• 有一个例外：人工牙根节点被允许多生几个孩子（那些孩子会成为起点的路径重新创建套）

显然，这将是不可能消除所有重复，但我想找到一个算法，找到最可能的淘汰。这是我不得不寻求帮助。我可以通过手工完成，但不能用正式的算法来表达它，这在所有情况下都可行）。

编辑：但愿这个小例子说明了这个问题更好：

我们有三个列表，list0 = [0,3,4,7,8], list1 = [1,2,3,6,7], list3 = [5,6,7,8]。这些列表的索引是来自根节点R的第一条边的标题。在这个第一个边缘之后，导致到没有子节点的节点（在这个例子中它是所有三个节点的同一个节点，但不一定是这种情况）。此路径上节点的所有标题都与相应的索引一起构成列表。

正如您所看到的，值7出现三次，值3,6和8每次两次。所以最好的情况是摆脱5个不必要的节点。但是，根据我们的条件，没有节点可以有多于一个孩子，并不总是可以摆脱所有重复。下图显示了一个可能的解决方案，其中重复的6和8无法解析。 [边注：6或8可以与3进行交换，并且仍然具有一个12节点溶液]

Answer 1

我不知道现有算法来解决这个，但我认为我看到了一些攻击。首先，将您的图形颠倒并使其成为一棵简单的树，以为根。接下来，请注意您的“列表”是无序的：它们会更好地工作（假设没有值的重复）。

附注：你可以可以转换为单根问题 - 只需为每个集合添加一个新的唯一符号。这将自动成为根节点。

现在你可以用更像决策树的东西来攻击它。子树的递归算法将产生可用的解决方案。您在分解的偏好尝试首先应该由直觉来驱动，如

• 最频繁出现在子树的套
• 所有集合的最大公共子集的值。
• 将从问题中删除最多元素的子集。例如，3个子集中的3个子集比2个子集中的4个子集更好。

最后一项不是在CS 101中解决的问题，它不是第一次罢工时保证的最佳解决方案。在过去的24小时内，我大部分都相信自己，没有一个简单的单一攻击能够为您提供所有输入的最佳解决方案。