CODEWITHSUNDEEP
pythonsubset
RMS
RMS

Reputation: 13

Can someone explain this logic of finding all subsets of a set in Python?

I came across this solution to find the subsets of a set in Python. I could not fully grab the logic. Can some explain it?

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]]

Upvotes: 0

Views: 54

Answers (1)

AKX
AKX

Reputation: 168903

The core idea is to exploit the binary representations of integers and check the j th bit of the iterator integer i for each element in the iterable. The algorithm works for any iterable, not just sets, by the way.

Here's a verbose version that prints out each step of the deduction:

  • The "combination index" and its binary representation on the === header line
  • Test result for each member index in x: the index in decimal, the index in binary, whether the memberindex'th bit in the combination index is set, and the member itself
  • The resulting combination on the -> line
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"])

prints out

=== 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']

Upvotes: 1

Related Questions