trjhtr

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]) + 'nn')

• 
  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!