有没有一个标准算法可以找到列表项的并集？

Question

有没有一个标准算法可以找到列表项的并集？

3

我不确定应该如何称呼这个算法，这也是我不确定它是否已经存在的原因之一。

（注：我使用了一些宏来简化输入以进行说明）

std::vector<BYTE> itemlist;

itemlist.push_back( 1000 );
itemlist.push_back( 0001 );
itemlist.push_back( 0001 );
itemlist.push_back( 0010 );
itemlist.push_back( 0100 );
itemlist.push_back( 0011 );
itemlist.push_back( 0001 );
itemlist.push_back( 1000 );

std::list<std::vector<int>> results = Confab(itemlist);

期望结果：

{ [ 1,2,3,5,6], [4], [0,7] }

所以我使用BYTE作为位掩码来查找成员的并集。关键是我也更新了掩码。所以第1和第2项没有共同点，但第5项可以与任何一项合并。

我正在寻找如何在最少的通行证中执行此操作的任何见解。在现实世界中，我使用DWORDs。

编辑：我忘记提到任何具有0000的项目都意味着该项目获得自己的条目。

- Ben L

看起来你正在尝试将一个集合分割成多个子集，其中每个结果集的成员都符合 (a ^ b) & a == a 的条件。是这样吗？ - Zac Howland

2

你的声望值太“圆滑”了...我发现很难给它点赞... - Sinkingpoint

1

我现在需要一些时间来弄清楚你对那些位的意思。现在我明白了：你要找的是叫做“并查集”或“不相交集合”的东西。它可以用树实现。 - leemes

2个回答

0

“不相交集合”是一种非常通用的方法（http://en.wikipedia.org/wiki/Disjoint-set_data_structure）。这里也可以使用一些适应性。

一种可能的方法：

考虑一个列表A = {1000, 0100, 0010, 0001} - 每个元素表示一个集合，开始时所有集合都是不相交的。
对于列表中的每个元素v（如1010），在A中找到相应的集合（所有e在A中，使得e & v != 0）。
连接那些元素e1，e2，...：从A中删除它们，并将e1|e2|...添加到A中。

最后，A表示所有集合。您可以通过找到A中的a，使得a & e == e，来对每个项目e进行分类。

- Łukasz Kidziński

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bernhard Barker · Accepted Answer

从一个长度为所需比特数的指针数组开始，最初每个指针都为空。

对于每个元素：

如果没有设置对应位的任何数组元素，则创建一个新列表并将所有数组元素设置为指向该列表。
否则，对于每个初始化的数组元素，合并列表，使指针指向新列表。还将所有未初始化的数组元素设置为新列表。
将自增值添加到新列表中。

遍历数组，输出所有唯一的列表（为了仅处理唯一列表，可以在处理列表后设置某个指示器，以便不重复处理它）。

哦对了，我们还需要并查集 - 否则合并列表可能会导致一些其他元素指向旧列表。

关于并查集算法的更多信息：

这个算法使用了一些树数据结构组成的森林，但与标准的树结构不同，其中子节点指向父节点，而父节点可以有任意数量的子节点。我们从只包含每个集合中一个元素的树开始（因此，在我们创建新列表时，我们将创建一个新集合）。根节点可以被视为整个树所属的集合的指示器。要合并两个集合，我们使其中一个根节点指向另一个根节点，以便在另一个根节点下合并树。

在我们的情况下，我们还将每个根节点存储一个元素列表。每当我们想按上述规定合并列表时，我们首先遍历每棵树以查看它属于哪个集合，并在它们属于不同集合时合并集合（及其列表），否则不执行任何操作。

这只是对并查集的基本描述，如果您在理解这里的某些复杂性方面感到困难，您可能需要进一步阅读它。

运行时间分析：

您可以在常数时间内合并列表（请参见list::splice）。对于32位，总共永远不会有超过31个合并，因为永远不会有比位数更多的集合，因此也就没有比位数更多的列表，所以您只需要进行大部分的检查即可。

并查集算法的额外复杂度在这里应该是可以忽略不计的，特别是如果您使用了一些众所周知的优化方法。

如果正确实现（渐进地），这将与输入元素数量乘以位数成线性关系，这是最好的情况，因为您至少需要查看输入中每个元素的每个位。 示例：（出于简单起见，不显示并查集）

4位，因此是一个由4个列表组成的数组。

[NULL,NULL,NULL,NULL]

处理 1000。第一位未设置，因此创建一个包含0的新列表，并使该元素指向它。

 [0]
  ^
  |
[   ,NULL,NULL,NULL]

进程 0001。最后一位没有设置，因此创建一个包含 1 的新列表，并使该元素指向它。

 [0]           [1]
  ^             ^
  |             |
[   ,NULL,NULL,   ]

进程 0001。最后一位已经设置，所以只需加上 2。

 [0]           [1,2]
  ^             ^
  |             |
[   ,NULL,NULL,   ]

处理 0010。倒数第二位没有被设置，因此创建一个新列表，其中包含 3 并使该元素指向它。

 [0]      [3] [1,2]
  ^        ^   ^
  |        |   |
[   ,NULL,   ,   ]

处理 0100。第二位没有设置，因此创建一个包含4的新列表，并使该元素指向它。

 [0] [4] [3] [1,2]
  ^   ^   ^   ^
  |   |   |   |
[   ,   ,   ,   ]

处理 0011。倒数第二位和最后一位被设定，因此将它们合并并加上5。

 [0] [4] [1,2,3,5]
  ^   ^   ^   ^
  |   |   |   |
[   ,   ,   ,   ]

进程 0001。最后一位被设置了，所以只需加上6。

 [0] [4] [1,2,3,5,6]
  ^   ^   ^   ^
  |   |   |   |
[   ,   ,   ,   ]

处理 1000。第一位被设置了，所以只需加上 7。

 [0,7] [4] [1,2,3,5,6]
  ^     ^   ^   ^
  |     |   |   |
[   ,     ,   ,   ]

现在我们已经有了三个列表，符合要求。