The Beauty of Recursion

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
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s