Recursive implementation of power set in Python

Question

I was doing a recursion problem called power set, and would like to get code review. Here's the problem.

# Power Set:   Given a set S, return the powerset P(S), which is
#           a set of all subsets of S.
#
# Input:    A String
# Output:   An Array of String representing the power set of the input
#
# Example:  S = "abc", P(S) = ['', 'a', 'b', 'c', 'ab', 'ac', 'bc', 'abc']
#
# Note:     The input string will not contain duplicate characters
#           The letters in the subset string must be in the same order
#           as the original input.

I also draw out an example of recursive tree in the following example:

# input: "abc" 
# output: ["", "a", "b", "c", "ab", "ac", bc", "abc"] 
2 * 2 * 2  = 8  total
_  _   _    
#  index 
#  a  b  c
#                                          "",i=0
#                      /                                           \ 
#                       "a",i=1                                   "", i= 1 
#                  /           \                           /                  \ 
#              "ab",i=2          "a",i=2                 "b", i=2             "" i=2 
#              /    \            /      \                /     \              /       \ 
#        "abc", i=3 "ab", i=3  "ac",i=3  "a", i=3   "bc", i=3  "b", i=3     "c", i=3  "", i = 3 
#         ret        ret         ret        ret        ret         ret      ret          ret 

# result = ["abc", "ab", "ac", "a", "bc", "b", "c", ""]

python solution

def powerset(input):
    results = []

    def recurse(build, depth):
        if (depth == len(input)):
            results.append(build)
            return

        recurse(build, depth + 1)
        recurse(build + input[depth], depth + 1)

    recurse('', 0)
    return results

The solution passes all of the tests.

# ###########################################################
# ##############  DO NOT TOUCH TEST BELOW!!!  ###############
# ###########################################################


from cStringIO import StringIO
import sys


# custom expect function to handle tests
# List count : keeps track out how many tests pass and how many total
#   in the form of a two item array i.e., [0, 0]
# String name : describes the test
# Function test : performs a set of operations and returns a boolean
#   indicating if test passed
def expect(count, name, test):
    if (count is None or not isinstance(count, list) or len(count) != 2):
        count = [0, 0]
    else:
        count[1] += 1

    result = 'false'
    errMsg = None
    try:
        if test():
            result = ' true'
            count[0] += 1
    except Exception, err:
        errMsg = str(err)

    print('  ' + (str(count[1]) + ')   ') + result + ' : ' + name)
    if errMsg is not None:
        print('       ' + errMsg + '\n')


# code for checking if lists contain the same elements
def lists_matching(lst1, lst2):
    if len(lst1) != len(lst2):
        return False

    cache = {}
    for i in xrange(0, len(lst1)):
        if lst1[i] in cache:
            cache[lst1[i]] += 1
        else:
            cache[lst1[i]] = 1
    for j in xrange(0, len(lst2)):
        if lst2[j] not in cache or cache[lst2[j]] == 0:
            return False
        cache[lst2[j]] -= 1
    return True


print('Powerset Tests')
test_count = [0, 0]


def test():
    example = powerset('abc')
    return (example is not None and lists_matching(example,
            ['', 'a', 'b', 'c', 'ab', 'bc', 'ac', 'abc']))


expect(test_count, 'should work on example input abc', test)


def test():
    example = powerset('')
    return example is not None and lists_matching(example, [''])


expect(test_count, 'should work on empty input', test)


def test():
    example = powerset('ab')
    return (example is not None and
            lists_matching(example, ['', 'a', 'b', 'ab']))


expect(test_count, 'should work on two-letter input', test)


def test():
    example = powerset('abcdefg')
    solution = ['', 'g', 'f', 'fg', 'e', 'eg', 'ef', 'efg', 'd', 'dg', 'df',
                'dfg', 'de', 'deg', 'def', 'defg', 'c', 'cg', 'cf', 'cfg',
                'ce', 'ceg', 'cef', 'cefg', 'cd', 'cdg', 'cdf', 'cdfg', 'cde',
                'cdeg', 'cdef', 'cdefg', 'b', 'bg', 'bf', 'bfg', 'be', 'beg',
                'bef', 'befg', 'bd', 'bdg', 'bdf', 'bdfg', 'bde', 'bdeg',
                'bdef', 'bdefg', 'bc', 'bcg', 'bcf', 'bcfg', 'bce', 'bceg',
                'bcef', 'bcefg', 'bcd', 'bcdg', 'bcdf', 'bcdfg', 'bcde',
                'bcdeg', 'bcdef', 'bcdefg', 'a', 'ag', 'af', 'afg', 'ae',
                'aeg', 'aef', 'aefg', 'ad', 'adg', 'adf', 'adfg', 'ade',
                'adeg', 'adef', 'adefg', 'ac', 'acg', 'acf', 'acfg', 'ace',
                'aceg', 'acef', 'acefg', 'acd', 'acdg', 'acdf', 'acdfg',
                'acde', 'acdeg', 'acdef', 'acdefg', 'ab', 'abg', 'abf', 'abfg',
                'abe', 'abeg', 'abef', 'abefg', 'abd', 'abdg', 'abdf', 'abdfg',
                'abde', 'abdeg', 'abdef', 'abdefg', 'abc', 'abcg', 'abcf',
                'abcfg', 'abce', 'abceg', 'abcef', 'abcefg', 'abcd', 'abcdg',
                'abcdf', 'abcdfg', 'abcde', 'abcdeg', 'abcdef', 'abcdefg']
    return example is not None and lists_matching(example, solution)


expect(test_count, 'should work on longer input', test)

print('PASSED: ' + str(test_count[0]) + ' / ' + str(test_count[1]) + '\n\n')

Answer 1

• input is a library function. Use a different variable name.
• Python comes with the methods itertools.combinations, which can generate all combinations of given size.

The function can be compressed to:

from itertools import combinations

def powerset(input_set):
    result = []
    for size in range(len(input_set) + 1):
        result += combinations(input_set, size)
    return result

---

If you want the result to be strings, instead of tuples of combinations; use a join:

result += [''.join(c) for c in combinations(input_set, size)]

---

Use the unittest module to write/generate test cases. The current method you've been following [1] [2] is neither maintainable nor readable in the long run!