algorithm - 将集合合并成有向图

Question

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

我的目标不是将这些集合表示为列表，而是树状结构，这样我就可以消除多个集合共享的整数元素。该结构是具有人工根节点的有向图。其他节点是在集合中找到的整数。根节点最多有 n 个子节点(n 是集合的数量)。这些 child 实际上是来自不同集合的第一个整数，必须由算法添加。有几个条件:

• 必须有可能通过树中的一条路径重新创建这样的集合。
• 通过树的路径必须是明确的，每个顶点都不能有多个 child 。
• 有一个异常(exception):人工根节点允许有多个子节点(这些子节点将是重新创建集合的路径的起点)

显然，不可能消除所有重复项，但我想找到一种算法，找到最可能的消除。这是我必须寻求帮助的地方。我可以手工完成，但不能用适用于所有情况的正式算法来表达。

编辑:希望这个小例子能更好地说明问题:

我们有三个列表，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

我不知道现有的算法可以解决这个问题，但我认为我看到了一些攻击。首先，将你的图表倒过来，使它成为一棵简单的树，以 7 为根。接下来，请注意您的“列表”是无序的:它们作为集合会更好地工作(假设没有重复的值)。

旁注:您可以将其简单地转换为单根问题——只需向每个集合添加一个新的、唯一的符号。这将自动成为根节点。

现在您可以使用更像是决策树的东西来解决这个问题。子树的递归算法将产生可用的解决方案。您对首先尝试哪种分解的偏好应该由启发式驱动，例如

• 子树集合中出现频率最高的值
• 所有集合的最大公共(public)子集。
• 将从问题中删除最多元素的子集。例如，3 个集合的 3 成员子集比只有 2 个集合的 4 成员子集更好。

这最后一项不是您在 CS 101 中解决的问题，也不是保证第一次攻击的最佳解决方案。在过去的 24 小时内，我基本上说服自己，没有直接的、单一的攻击可以为所有输入提供最佳解决方案。