4
\$\begingroup\$

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')
\$\endgroup\$
5
\$\begingroup\$
  • 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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.