根据位出现查找集合

Question

我正在尝试查找出现不止一次的位列。让我举个例子：

       X Y Z   
Set A  0 1 0
Set B  0 0 1
Set C  0 1 0
Set D  0 0 0

通过 UNION 操作，我能够知道集合列表中的哪个 COLUMN 的位设置为 1。如果我执行 A UNION B UNION C UNION D 然后我们得到 0 1 1 ，这意味着 X 列没有位设置为 1，Y 列和 Z 列至少有 1 个位设置为 1。

我的问题是我正在尝试找到正确的设置操作来查找多次将位设置为 1 的列。在上面给出的例子中，Y 列有 2 位设置为 1。因此结果应该是 0 1 0.

我尝试做交叉点，这是最合乎逻辑的事情，但产生了不同的结果。

我很感激有人可以指导我应该执行哪些集合操作组合以获得所需的结果。提前致谢。

Answer 1

让USet_0 := 0 0 0和DSet_0 := 0 0 0。然后我们定义

USet_(k+1) := USet_k UNION Set_k | forall 0 <= k < n

和

DSet_(k+1) := DSet_k UNION (USet_k INTERSECT Set_k) | forall 0 <= k < n

找到所有 n 集的并集的操作然后产生 USet_n。任何设置了多个位的列然后由 DSet_n.

表示

Answer 2

My problem is I'm trying to find the right set operation to find columns that has bits set to 1 more than once.

这是一种方法：

(A ∩ B) ∪ (A ∩ C) ∪ (A ∩ D) ∪ (B ∩ C) ∪ (B ∩ D) ∪ (C ∩ D)

也就是说，数学非常灵活；你可以从字面上直接说 "the set containing all elements that appear in at least two of the sets A, B, C, D"，数学家在大多数情况下都会接受它。

Answer 3

当你尝试高效地做这件事时，这会更有趣。

从 0 开始按顺序为每组分配编号。

那么，如果有一个列在至少两个不同的集合中，那么这两个集合的数字一定是不同的，如果数字不同，那么这些数字的二进制表示将不同至少一位位置。

所以：

对于集合数中的每个位位置b（其中有log(number_of_sets)）：
1. 创建所有在其编号中设置了位 b 的集合的并集；
2. 创建所有 not 的集合的并集 b 在它们的数字中设置了位；
3. 将这两个集合相交。
创建所有这些交集的并集。

完成。结果是出现在至少 2 个不同集合中的所有列的集合。

例如，如果列在集合5和集合7中，那么它将在位位置b=1（位值2），因为5(101)和[=的二进制表示36=]7 (111) 那个位的位置不同。该列将在所有具有 1 位的数字集合的并集中，and 在具有位 [=] 的所有集合的并集中36=]1 上.

所需的集合操作总数为N*log(N)，其中N为集合数。

Finding a Set based on Bit Occurence