c++ - 是否有用于查找列表项并集的标准算法

Question

我不确定如何称呼此算法，所以这也是我不确定它是否已经存在的部分原因。

(注意:出于说明目的，我正在使用一些宏来简化输入)

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 项与其中任何一项合并。

我正在寻找有关如何以最少的遍数完成此操作的任何见解。在现实世界中，我使用的是 DWORD。

edit 我忘了提到任何带有 0000 的项目都意味着该项目有自己的条目。

Answer 1

从一个列表指针数组开始，该数组等于您拥有的位数，由空指针组成。

对于每个元素:

• 如果没有设置bits对应的数组元素，则新建一个list，并设置所有数组元素指向list。

• 否则，对于每个已初始化的数组元素，合并列表，使指针指向新列表。还将所有未初始化的数组元素设置为新列表。

• 向新列表添加一个自动递增的值。

遍历数组，输出所有唯一列表(只处理唯一列表，你可以在处理完列表后设置一些指示符，这样你就不会处理它两次)。

对了，我们还需要union-find此处 - 否则合并列表可能会留下一些指向旧列表的其他元素。

关于 union 查找算法的更多信息:

该算法使用森林(一堆树数据结构)，但不是父项指向子项的标准树格式，而是子项指向其父项，父项可以有任意数量的子项。我们从一棵树开始，每个集合只包含一个元素(因此，在我们的例子中，每当我们创建一个新列表时，我们都会创建一个新集合)。可以将根视为整棵树所属集合的指示符。为了合并两个集合，我们让一个根指向另一个根，这样树就会在另一个根下合并。

在我们的例子中，我们会让每个根也存储一个元素列表。每当我们想要按照上面指定的方式合并列表时，我们首先会遍历每棵树以查看它属于哪个集合，如果集合(及其列表)属于不同的集合，则合并它们，否则什么也不做。

这只是 union-find 的基本描述，如果您难以理解这里的一些复杂性，您可能需要进一步阅读它。

运行时间分析:

您可以在恒定时间内合并列表(参见 list::splice )。对于 32 位，合并的总数永远不会超过 31 次，因为集合(即列表)的数量永远不会超过位数，因此您大部分时间都在进行检查。

union-find 算法增加的复杂性在这里应该可以忽略不计，特别是如果您使用一些众所周知的优化。

这(如果实现正确)在位数乘以输入元素的数量上是线性的，你不能做得比(asymptotically 说的)更好，因为你至少需要查看每个元素的每一位输入中的元素。

示例:(为简单起见，未显示 union 查找)

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]
  ^     ^   ^   ^
  |     |   |   |
[   ,     ,   ,   ]

现在我们根据需要有了 3 个列表。