在 Java 中使用位操作的集合的所有可能子集

Question

我们如何使用 Java 中的位操作生成集合的所有可能子集？例如，如果我们有一个 int 数组 [1, 2, 3]，所有可能的子集是：

[            
  [3],       
  [1],       
  [2],       
  [1,2,3],   
  [1,3],     
  [2,3],     
  [1,2],     
  []         
]

Answer 1

从 0 数到 (2^set.size() - 1)（含）。检索与当前计数中的 1 位对应的元素。当然，必须对集合进行排序才能按索引检索元素。

唯一棘手的部分是取出与当前计数中的1位对应的元素。这是一种方法的伪代码：

for (int pos = 0, mask = 1; mask <= currentCount; mask <<= 1; ++pos) {
    if ((currentCount & mask) != 0) {
        include element at pos in the current subset
    }
}

请注意，这假定原始集合大小不超过您用于计数和掩码的任何整数类型的可用位数。

Answer 2

这是我从 this 网站上提取的代码。还有关于字节表示的进一步解释：

private static void findSubsets(int array[]) {
    int numOfSubsets = 1 << array.length;

    for (int i = 0; i < numOfSubsets; i++) {
        int pos = array.length - 1;
        int bitmask = i;

        System.out.print("{");
        while (bitmask > 0) {
            if ((bitmask & 1) == 1)
                System.out.print(array[pos] + ",");
            bitmask >>= 1;
            pos--;
        }
        System.out.print("}");
    }
}

在 Java 中使用位操作的集合的所有可能子集

All possible subsets of a set using bit manipulations in Java

java

bit-manipulation

subset