I was trying to write a snippet of code to generate all the subsets of a given set, in python. My thoughts were along the following lines:

- Have a number run from 0 to 2^n – 1 where n is the number of elements in the set.
- In each run, look at the binary representation of the number and select all the elements from the list whose corresponding bits (w.r.t their positions) are set to 1.
- At the end, return this list of lists, which is the power set.

The code looks like this:

def getBinaryString(i):
'''
returns the binary format of i in string format
'''
if i == 0 or i == 1:
return str(i)
binary = ""
while i > 0:
binary = binary + str(i%2)
i = i/2
return binary
def getListSubset(L, i):
"""
Takes i and returns the corresponding elements in the binary
representation of i
"""
ithSubset = []
if i == 0:
return []
binary = getBinaryString(i)
# print "binary string is: " + binary
length = 0
while length < len(binary):
if binary[length] == '1':
ithSubset.append(L[length])
length += 1
return ithSubset
def generateAllSubsets(L):
"""
Returns a list of all subsets of L
"""
allSubSets = []
listLen = len(L)
i = 0
# print listLen
while i < 2 ** listLen:
aSubset = getListSubset(L, i)
allSubSets.append(aSubset[:])
i += 1
print "Total number of subsets: " + str(len(allSubSets))
return allSubSets

Its not that bad a piece of code, after all, but still, it is not as elegant as this beautiful recursive version:

When I looked at the recursive version, it just blew me out. I was convinced that thinking recursively is an art and beauty belies it.

def genRecursiveSubsets(L):
'''
generates all the subsets recursively (i.e. beautifully)!
'''
if len(L) == 0:
return [[]]
smaller = genRecursiveSubsets(L[:-1])
extra = L[-1:]
new = []
for small in smaller:
new.append(small + extra)
return new + smaller

### Like this:

Like Loading...

*Related*