时间戳

首页 > 解决方案 > 有人可以解释这种在 Python 中查找集合的所有子集的逻辑吗？

python - 有人可以解释这种在 Python 中查找集合的所有子集的逻辑吗？

问题描述

我遇到了这个解决方案来在 Python 中查找集合的子集。我无法完全掌握逻辑。有人可以解释一下吗？

f = lambda x: [[y for j, y in enumerate(set(x)) if (i >> j) & 1] for i in range(2**len(set(x)))]
f([1,2,3])

Output:
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

标签： pythonsubset

解决方案

核心思想是利用整数的二进制表示并检查迭代器整数中每个元素的j第 th 位。i顺便说一下，该算法适用于任何可迭代的，而不仅仅是集合。

这是一个详细的版本，打印出每一步的演绎：

  • ===标题行上的“组合索引”及其二进制表示
  • 中每个成员索引的测试结果x：十进制索引，二进制索引，是否设置了组合索引中的第memberindex位，成员本身
  • 结果组合就->行了
def combinations(x):
    for i in range(2 ** len(x)):
        print(f"=== {i} / {i:08b}")
        result = []
        for j, member in enumerate(x):
            flag = (i >> j) & 1
            print(j, f"{j:08b}", flag, member)
            if flag:
                result.append(member)
        print("-> ", result)


combinations(["foo", "bar", "fjord"])

打印出来

=== 0 / 00000000
0 00000000 0 foo
1 00000001 0 bar
2 00000010 0 fjord
->  []
=== 1 / 00000001
0 00000000 1 foo
1 00000001 0 bar
2 00000010 0 fjord
->  ['foo']
=== 2 / 00000010
0 00000000 0 foo
1 00000001 1 bar
2 00000010 0 fjord
->  ['bar']
=== 3 / 00000011
0 00000000 1 foo
1 00000001 1 bar
2 00000010 0 fjord
->  ['foo', 'bar']
=== 4 / 00000100
0 00000000 0 foo
1 00000001 0 bar
2 00000010 1 fjord
->  ['fjord']
=== 5 / 00000101
0 00000000 1 foo
1 00000001 0 bar
2 00000010 1 fjord
->  ['foo', 'fjord']
=== 6 / 00000110
0 00000000 0 foo
1 00000001 1 bar
2 00000010 1 fjord
->  ['bar', 'fjord']
=== 7 / 00000111
0 00000000 1 foo
1 00000001 1 bar
2 00000010 1 fjord
->  ['foo', 'bar', 'fjord']

推荐阅读