英文:
Power set of an input set as custom collection
问题
我一直在阅读《Effective Java》这本书，现在卡在了这段代码上，我无法理解这段代码是如何生成幂集的。
**代码:**
```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]]
有人可以解释一下这段代码是如何生成给定集合的幂集吗？
<details>
<summary>英文:</summary>
I have been reading the Effective Java book and I have stuck with this code I am unable to understand how this code is generating power set.
**Code:**
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);
}
}
**Output:**
[[], [a], [b], [a, b], [c], [a, c], [b, c], [a, b, c]]
Can someone explain how this code is generating powerset of a given set.
</details>
# 答案1
**得分**: 1
代码使用索引号的二进制表示作为`s`列表中要包含的元素的映射。
例如，假设一个数字中只有3个位：
```plaintext
索引 | a | b | c
-------------------
0 (000) | 0 | 0 | 0 -> 不选择任何元素
1 (001) | 0 | 0 | 1 -> 仅选择 c
2 (010) | 0 | 1 | 0 -> 仅选择 b
3 (011) | 0 | 1 | 1 -> 选择 a 和 b
4 (100) | 1 | 0 | 0 -> 仅选择 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时终止，即没有更多的位要进行移位/添加的元素了
以 index = 3 为例：
i | index | (index & 1) == 1 | 添加的元素
-----------------------------------------
0 | 011 | TRUE | a (第0个元素)
1 | 001 | TRUE | b (第1个元素)
2 | 000 | FALSE | -
(当 index == 0 时终止)
英文:
The code uses the binary representation of the index number as a map of which element of s to include.
For instance, assuming only 3 bits in a number:
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
...
The get method of the generated list follows this logic with the index input given:
index >>= 1shifts all bits one position to the right with each loop(index & 1) == 1checks whether the rightmost bit ofindexis a 1
The & operator is the binary AND, so 2 & 1 equals binary 010 AND 001, giving 000 (not equal to 1 or 001) and 3 & 1 equals binary 011 AND 001, giving 001 (equal to 1 or 001)
- If this evaluates to true, the
i-th element is added to the list - This terminates when
index == 0, i.e. there are no more bits to shift / elements to add
Example for index = 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)
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论