是否有一个好的数据结构来查找给定位集的所有存储子集？
Is there a good data structure for finding all stored subsets of a given bitset?
设 X 是一组不同的 64 位无符号整数 std::uint64_t，每个整数都被解释为表示 {1,2,...,64} 子集的位集。
我想要一个函数做以下事情：给定一个std::uint64_tA，不一定在X中，列出X中的所有B，这样B 是 A 的子集，当 A、B 被解释为 {1,2,...,64} 的子集时。
（当然，在C++中这个条件就是(A & B) == B）。
由于A本身不需要在X中，我相信这不是其他问题的重复。
X 会随着时间增长（但不会删除任何内容），尽管对 X 的查询将远远多于添加。
我可以自由选择表示 X 元素的数据结构。
显然，我们可以将 X 表示为 std::set 或 std::uint64_t 的排序 std::vector，我在下面给出了一种算法。但是我们可以做得更好吗？
X 和算法 有效执行此操作的良好数据结构是什么？ 这应该是一个标准问题，但我找不到任何东西。
编辑： 对不起，如果这太含糊了。显然，如果 X 是 std::set，我们可以搜索 A 的所有子集，花费时间 O(2^m log |X|) 且 m <= N，或者 X 的所有元素时间 O(|X|日志 |X|).
假设在大多数情况下，B 的数量比 2^m（A 的子集数量）和 |X| 都小很多。所以，我们想要某种算法 运行 的时间比 |X| 少得多或 2^m 在这种情况下，理想情况下是时间 O（B 的数量），但这肯定太乐观了。显然，O(|X|)在最坏的情况下是不能被打败的。
显然 X 的一些内存开销是预期的，并且 内存对我来说比时间 更不是瓶颈。使用大约 10 *（存储为 std::set 的 X 的内存）就可以了。远不止于此。 （渐近地，超过 O(|X|) 或 O(|X| log |X|) 的内存可能太多了）。
显然，使用 C++ 不是必需的：algorithms/data 结构在这里很重要。
在X固定的情况下，也许Hasse diagrams可以工作.
每次 X 增长时，构建 Hasse 图似乎非常耗时。 （但如果没有其他问题，也许仍然值得一试）。 编辑：也许更新没有那么慢，比我想象的要好。
以下只是我目前的想法；也许可以找到更好的东西？
最终编辑： 因为它已经关闭，所以可能相当 - “重复”问题非常接近 - 我不会再进行任何进一步的编辑。我可能会执行以下操作，但使用概率跳跃列表结构而不是 std::set，并增加跳跃距离（，因此您可以快速计算出间隔中剩余的 X 元素数量，从而通过在交叉点变小时切换到线性搜索来减少搜索间隔的数量)。这类似于 中给出的顺序统计树，但是跳过列表比 std::set 更容易重新实现（特别是因为我不需要删除 ).
将 X 表示为 std::set 或排序 std::vector 的 64 位无符号整数 std::uint64_t，使用普通数字顺序，并在更小的范围内进行递归搜索和更小的间隔。
例如，我的查询元素是A = 10011010。
包含第一位的 A 的子集位于包含区间 [10000000, 10011010].
中
包含第二位但不包含第一位的 A 子集位于区间 [00010000, 00011010].
第三位没有第二位的在[00001000, 00001010].
有第四位没有第三位的在[00000010, 00000010].
现在，在第一个区间 [10000000, 10011010] 内，您可以根据第二位搜索两个子区间：[10000000, 10001010] 和 [10010000, 10011010]。
因此你可以用这种方式递归分解它。搜索区间的总长度一直在变小，所以这肯定比通过所有 X 进行简单的线性搜索渐进地更好。
例如，如果 X = {00000010, 00001000, 00110111, 10011100} 那么只有第一个、第三个、第四个深度为 1 的区间与 X 有非空交集。最终返回的结果将是 [ 00000010, 00001000].
当然，如果X元素分布比较均匀的话，这是不平衡的。我们可能希望搜索间隔在每个深度处具有大致相等的宽度，但事实并非如此；上面，四个深度 1 搜索间隔的大小，我认为是 27、11、3、1，对于更大的 N，差异可能更大。
如果查询集A中有k位，那么你将不得不在深度1处构造k个初始搜索区间（在ONE位上搜索），然后在深度处构造最多2k个搜索区间2、4k深度3等
如果我没记错的话，因为日志 |X| = O(N) 搜索间隔的数量是 O(k + 2k + 4k + ... + 2^n . k) = O(k^2) = O(N^2)，其中 2^n = O (k)，每一个都需要 O(N) 的时间来构建（实际上要少一些，因为它是较小数字的对数，但对数不会增加太多），所以看起来这是一个 O(N^ 3) 构造搜索区间的算法。
当然完整的算法不是O(N^3)，因为每个区间可能包含很多元素，所以将它们全部列出一般不会比O(2^N)好，但是让我们忽略这一点并假设 X 中没有足够的元素来压倒 O(N^3) 估计。
另一个问题是 std::map 不能告诉你有多少元素位于一个区间内（不像排序的 std::vector）所以你不知道什么时候中断划分并搜索区间中所有剩余的 X 元素。当然，你对 X 元素的数量（整个区间的大小）有一个上限，但它可能很差。
编辑：另一个 std::set 的结构，它也可以快速为您提供元素的数量范围，这显然可以适应 std::map-like 结构。这对于 p运行ing 很有效（虽然很烦人，但对于 C++，您必须重新实现大部分 std::map!)
解决方案
将整数视为 0 和 1 的字符串，使用以下规则构建 patricia tree 的自定义版本：
- 在查找过程中，如果
1是一个分支的当前输入位，则继续向下两个个子树
到达的所有有效叶节点的集合将是答案。
复杂性
令 n 为 X 的大小，
时间：O(n)
- 最坏情况
-1，遍历所有子树。复杂性受节点总数的约束，如下所述
Space: O(n)
- 一棵帕特里夏树的节点数正好是 2n - 1
理由
假设你的匹配条件是(A & B) == B，那么真理table是：
.
A0
A1
B0
T
T
B1
F
T
因此，在查找过程中，当输入位为 1 时，我们在分支节点上收集两个子树。
设 X 是一组不同的 64 位无符号整数 std::uint64_t，每个整数都被解释为表示 {1,2,...,64} 子集的位集。
我想要一个函数做以下事情：给定一个std::uint64_tA，不一定在X中，列出X中的所有B，这样B 是 A 的子集，当 A、B 被解释为 {1,2,...,64} 的子集时。
（当然，在C++中这个条件就是(A & B) == B）。
由于A本身不需要在X中，我相信这不是其他问题的重复。
X 会随着时间增长（但不会删除任何内容），尽管对 X 的查询将远远多于添加。
我可以自由选择表示 X 元素的数据结构。
显然，我们可以将 X 表示为 std::set 或 std::uint64_t 的排序 std::vector，我在下面给出了一种算法。但是我们可以做得更好吗？
X 和算法 有效执行此操作的良好数据结构是什么？ 这应该是一个标准问题，但我找不到任何东西。
编辑： 对不起，如果这太含糊了。显然，如果 X 是 std::set，我们可以搜索 A 的所有子集，花费时间 O(2^m log |X|) 且 m <= N，或者 X 的所有元素时间 O(|X|日志 |X|).
假设在大多数情况下，B 的数量比 2^m（A 的子集数量）和 |X| 都小很多。所以，我们想要某种算法 运行 的时间比 |X| 少得多或 2^m 在这种情况下，理想情况下是时间 O（B 的数量），但这肯定太乐观了。显然，O(|X|)在最坏的情况下是不能被打败的。
显然 X 的一些内存开销是预期的，并且 内存对我来说比时间 更不是瓶颈。使用大约 10 *（存储为 std::set 的 X 的内存）就可以了。远不止于此。 （渐近地，超过 O(|X|) 或 O(|X| log |X|) 的内存可能太多了）。
显然，使用 C++ 不是必需的：algorithms/data 结构在这里很重要。
在X固定的情况下，也许Hasse diagrams可以工作.
每次 X 增长时，构建 Hasse 图似乎非常耗时。 （但如果没有其他问题，也许仍然值得一试）。 编辑：也许更新没有那么慢，比我想象的要好。
以下只是我目前的想法；也许可以找到更好的东西？
最终编辑： 因为它已经关闭，所以可能相当 - “重复”问题非常接近 - 我不会再进行任何进一步的编辑。我可能会执行以下操作，但使用概率跳跃列表结构而不是 std::set，并增加跳跃距离（，因此您可以快速计算出间隔中剩余的 X 元素数量，从而通过在交叉点变小时切换到线性搜索来减少搜索间隔的数量)。这类似于 std::set 更容易重新实现（特别是因为我不需要删除 ).
将 X 表示为 std::set 或排序 std::vector 的 64 位无符号整数 std::uint64_t，使用普通数字顺序，并在更小的范围内进行递归搜索和更小的间隔。
例如，我的查询元素是A = 10011010。 包含第一位的 A 的子集位于包含区间 [10000000, 10011010].
中包含第二位但不包含第一位的 A 子集位于区间 [00010000, 00011010].
第三位没有第二位的在[00001000, 00001010].
有第四位没有第三位的在[00000010, 00000010].
现在，在第一个区间 [10000000, 10011010] 内，您可以根据第二位搜索两个子区间：[10000000, 10001010] 和 [10010000, 10011010]。
因此你可以用这种方式递归分解它。搜索区间的总长度一直在变小，所以这肯定比通过所有 X 进行简单的线性搜索渐进地更好。
例如，如果 X = {00000010, 00001000, 00110111, 10011100} 那么只有第一个、第三个、第四个深度为 1 的区间与 X 有非空交集。最终返回的结果将是 [ 00000010, 00001000].
当然，如果X元素分布比较均匀的话，这是不平衡的。我们可能希望搜索间隔在每个深度处具有大致相等的宽度，但事实并非如此；上面，四个深度 1 搜索间隔的大小，我认为是 27、11、3、1，对于更大的 N，差异可能更大。
如果查询集A中有k位，那么你将不得不在深度1处构造k个初始搜索区间（在ONE位上搜索），然后在深度处构造最多2k个搜索区间2、4k深度3等
如果我没记错的话，因为日志 |X| = O(N) 搜索间隔的数量是 O(k + 2k + 4k + ... + 2^n . k) = O(k^2) = O(N^2)，其中 2^n = O (k)，每一个都需要 O(N) 的时间来构建（实际上要少一些，因为它是较小数字的对数，但对数不会增加太多），所以看起来这是一个 O(N^ 3) 构造搜索区间的算法。
当然完整的算法不是O(N^3)，因为每个区间可能包含很多元素，所以将它们全部列出一般不会比O(2^N)好，但是让我们忽略这一点并假设 X 中没有足够的元素来压倒 O(N^3) 估计。
另一个问题是 std::map 不能告诉你有多少元素位于一个区间内（不像排序的 std::vector）所以你不知道什么时候中断划分并搜索区间中所有剩余的 X 元素。当然，你对 X 元素的数量（整个区间的大小）有一个上限，但它可能很差。
编辑：另一个 std::set 的结构，它也可以快速为您提供元素的数量范围，这显然可以适应 std::map-like 结构。这对于 p运行ing 很有效（虽然很烦人，但对于 C++，您必须重新实现大部分 std::map!)
解决方案
将整数视为 0 和 1 的字符串，使用以下规则构建 patricia tree 的自定义版本：
- 在查找过程中，如果
1是一个分支的当前输入位，则继续向下两个个子树
到达的所有有效叶节点的集合将是答案。
复杂性
令 n 为 X 的大小，
时间：O(n)
- 最坏情况
-1，遍历所有子树。复杂性受节点总数的约束，如下所述
Space: O(n)
- 一棵帕特里夏树的节点数正好是 2n - 1
理由
假设你的匹配条件是(A & B) == B，那么真理table是：
| . | A0 | A1 |
|---|---|---|
| B0 | T | T |
| B1 | F | T |
因此，在查找过程中，当输入位为 1 时，我们在分支节点上收集两个子树。