get all subsets of a set with format method?

Question

I have been searching the function to get all subsets of a set without importing anything. I found this code but I could not understand

def all_subsets(L=[1,2,3,4]):
  X = [format(x, '03b') for x in range(2**len(L))]   
  return [[L[i] for i in range(len(I)) if I[i]=='1'] for I in X]

can you explain this code or tell me a recursive function to get powerset of a list without importing anything

Does this answer your question? [How to get all subsets of a set? (powerset)](https://stackoverflow.com/questions/1482308/how-to-get-all-subsets-of-a-set-powerset) — Tomerikoo, Jan 05 '21 at 14:36
no because it is asked 11 years ago. so many things have changed. I could not find practical answer — Tarık, Jan 05 '21 at 15:11
Can you elaborate? There are 29 (!!!) answers there... The accepted imports `itertools`, and in case it's a problem for you, the second uses pure Python - 3 lines of code... What's outdated about it? — Tomerikoo, Jan 05 '21 at 15:37
[this one](https://stackoverflow.com/a/42739286/6045800) is from just 3 years ago, doesn't use any imports, and have clear explanations — Tomerikoo, Jan 05 '21 at 15:41

score 1 · Answer 1 · answered Jan 05 '21 at 14:34

The idea is to use binary numbers to represent if an element of the set is present. X is the array containing the binary representation of the numbers from 0 (empty subset) until 2^len(L) = 2^4 = 16 = 0x1111. An array of arrays is returned which contains the subsets using L[i] for each '1'.

score 1 · Answer 2 · answered Jan 05 '21 at 14:52

Lets first explain the idea,

For each subset, it can contain 0 to length(N) item. So, We can do the followings for L= [1,2,3,4]

First one, []
Pick only one element. i.e [1], [2], [3], [4]
Pick two elemens [1,2], [2,3], [3,4].
Pick three and so on

Now how can we do this programmatically, so that we consider all the subsets?

We can use a binary number counter. Consider a number as a string, and get the indexes where we have 1 in it. Now only include items from L for those indexes.

See below example,

000 -> No one, so, a subset = []

001 -> index `0` has one, L[0] = 1, so a subset = [1]

010 -> index `1` has one, L[1] = 2, so a subset = [2]

011 -> index `0`, `1` has one, L[0] = 1 L[1] = 2, so a subset = [1, 2]

100 -> index `2` has one, L[2] = 3, so a subset = [3]
....

This way we get all the subsets.

The above code does the followings,

Populates a list of binary number X up to 2^n (i.e 2^n is the total subset of an N length list)

X = [format(x, '03b') for x in range(2**len([1,2,3,4]))]

['000', '001', '010', '011', '100', '101', '110', '111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111']
Iterate each item on X list. For each item, iterate over each character and checks if it is 1. If yes, then include that index item from L to the result item.

[[L[i] for i in range(len(I)) if I[i]=='1'] for I in X]

This can be easily understandable by,

subsets = []
for I in X:
  for i in range(len(I)):
     if I[i]=='1':
       subsets.append([L[i])

get all subsets of a set with format method?

2 Answers2