创建BitSet的组合

Question

假设我有一个Java BitSet。我现在需要对BitSet进行组合，以便只有设置的位才能被翻转。即只需要所设置的比特的组合。

例如。BitSet - 1010，组合- 1010,1000,0010,0000

BitSet - 1100，组合- 1100,1000,0100,0000

我可以想到一些解决方案，例如，我可以取所有4位的组合，然后将这些组合与原始位集进行异或运算。但对于大型稀疏BitSets，这将是非常耗费资源的。所以我在寻找一个更优雅的解决方案。

Answer 1

看起来您想要获取位集的power set。关于如何获得Set<T>的电源设置，已经有了答案here。在这里，我将使用BitSets展示该帖子中所示算法的修改版本：

private static Set<BitSet> powerset(BitSet set) {
    Set<BitSet> sets = new HashSet<>();
    if (set.isEmpty()) {
        sets.add(new BitSet(0));
        return sets;
    }
    Integer head = set.nextSetBit(0);
    BitSet rest = set.get(0, set.size());
    rest.clear(head);
    for (BitSet s : powerset(rest)) {
        BitSet newSet = s.get(0, s.size());
        newSet.set(head);
        sets.add(newSet);
        sets.add(s);
    }
    return sets;
}

Answer 2

如果你意识到整数是计算机的“开”和“关”模式的内在变体，并且在适当的整数范围内迭代最终将产生所有可能的排列，则可以在单次线性传递中执行该操作，而不是递归。在您的情况下，唯一的挑战是将整数的密集压缩位传输到BitSet的目标位。

下面是这样一个解决方案：

static List<BitSet> powerset(BitSet set) {
    int nBits = set.cardinality();
    if(nBits > 30) throw new OutOfMemoryError(
        "Not enough memory for "+BigInteger.ONE.shiftLeft(nBits)+" BitSets");
    int max = 1 << nBits;
    int[] targetBits = set.stream().toArray();
    List<BitSet> sets = new ArrayList<>(max);
    for(int onOff = 0; onOff < max; onOff++) {
        BitSet next = new BitSet(set.size());
        for(int bitsToSet = onOff, ix = 0; bitsToSet != 0; ix++, bitsToSet>>>=1) {
            if((bitsToSet & 1) == 0) {
                int skip = Integer.numberOfTrailingZeros(bitsToSet);
                ix += skip;
                bitsToSet >>>= skip;
            }
            next.set(targetBits[ix]);
        }
        sets.add(next);
    }
    return sets;
}

它为迭代使用了一个Java值，这个值已经足以表示可以存储在int内置集合中的所有排列。如果您的源BitSet有2?位，则2？？可能的组合不仅需要100 GB的堆，而且还需要支持2?元素的集合，即不能表示为int的大小。

因此，如果数量超过了容量，上面的代码就会提前终止，甚至不需要尝试。您可以将其重写为使用long甚至BigInteger，以便在这种情况下保持忙碌，直到它使用OutOfMemoryError失败为止。

对于工作情况，int解决方案是最有效的变体。

请注意，代码返回一个List而不是一个HashSet，以避免散列的开销。已经知道这些值是唯一的，只有当您想要执行查找时，散列才会有回报，例如，使用另一个BitSet调用contains。但是要测试现有的BitSet是否是输入BitSet的排列，你甚至不需要生成所有的排列，一个简单的位操作，例如andNot已经告诉你了。因此，对于存储和迭代排列，ArrayList更有效。