创建 BitSet 的组合

Question

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

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

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

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

Answer 1

您似乎想获得有关如何获得 Set<T> 的幂集的 power set of the bit set. There is already an answer here。在这里，我将展示 post 中所示算法的修改版本，使用 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;
}

它使用 int 值进行迭代，这已经足以表示可以存储在 Java 的内置集合之一中的所有排列。如果您的源 BitSet 有 2³¹ 个一位，则 2³² 可能的组合不仅需要一百 GB 堆，而且还需要一个支持 2³² 元素的集合，即不能表示为 int.[=27= 的大小]

因此，如果数量超过能力，上面的代码会提前终止，甚至没有尝试。您可以重写它以使用 long 甚至 BigInteger 来代替，以使其在这种情况下保持忙碌，直到它无论如何都会因 OutOfMemoryError 而失败。

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

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

创建 BitSet 的组合

Creating combinations of a BitSet

java

combinations

bitset