我不确定如何称呼此算法,所以这也是我不确定它是否已经存在的部分原因。
(注意:出于说明目的,我正在使用一些宏来简化输入)
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 的项目都意味着该项目有自己的条目。
最佳答案
从一个列表指针数组开始,该数组等于您拥有的位数,由空指针组成。
对于每个元素:
如果没有设置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 个列表。
关于c++ - 是否有用于查找列表项并集的标准算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20982892/