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