输入集的幂集作为自定义集合

Question

我一直在阅读 Effective Java 这本书，但我一直坚持使用这段代码，我无法理解这段代码是如何生成功率集的。

代码：

public class PowerSet {

    public static final <E> Collection<Set<E>> of(Set<E> s) {
        List<E> src = new ArrayList<>(s);
        if (src.size() >= 30)
            throw new IllegalArgumentException("Set too big " + s);
        return new AbstractList<Set<E>>() {

            @Override
            public int size() {
                return 1 << src.size();
            }

            @Override
            public boolean contains(Object o) {
                return o instanceof Set && src.containsAll((Set) o);
            }

            @Override
            public Set<E> get(int index) {
                Set<E> result = new HashSet<>();
                for (int i = 0; index != 0; i++, index >>= 1)
                    if ((index & 1) == 1)
                        result.add(src.get(i));
                return result;
            }
        };
    }

    public static void main(String[] args) {
        Collection<Set<String>> result = of(Set.of("a", "b", "c"));
        System.out.println(result);
    }
}

输出：

[[], [a], [b], [a, b], [c], [a, c], [b, c], [a, b, c]]

谁能解释一下这段代码是如何生成给定集合的幂集的。

Answer 1

该代码使用索引号的二进制表示作为要包含 s 的哪个元素的映射。

例如，假设一个数字只有 3 位：

index   | a | b | c
--------------------
0 (000) | 0 | 0 | 0 -> take nothing
1 (001) | 0 | 0 | 1 -> take only c
2 (010) | 0 | 1 | 0 -> take only b
3 (011) | 0 | 1 | 1 -> take a and b
4 (100) | 1 | 0 | 0 -> take only a
...

生成列表的 get 方法遵循此逻辑，给定 index 输入：

index >>= 1 在每个循环中将所有位向右移动一位
(index & 1) == 1 检查 index 最右边的位是否为 1

& 运算符是二进制与，因此 2 & 1 等于二进制 010 AND 001，给出 000（不等于 1 或 001）和 3 & 1 等于二进制 011 AND 001，给出 001（等于 1 或 001）

如果计算结果为真，第 i 个元素将添加到列表中
这在 index == 0 时终止，即没有更多的位要移动/元素要添加

索引示例 = 3:

i | index | (index & 1) == 1 | element added
---------------------------------------------
0 |   011 |             TRUE |   a (0-th element)
1 |   001 |             TRUE |   b (1-th element)
2 |   000 |            FALSE |   - 
(terminates as index == 0)

输入集的幂集作为自定义集合

Power set of an input set as custom collection

java

set

powerset