print powerset of a string

Question

I'm trying to write python code to print the powerset of a string, but am running into some bugs. Here's what I've got:

def getperm (string):
    perm = []
    if len(string) == 0:
        perm.append("")
        return perm
    #if len(string) == 1:
    #   perm.append(string)
    #   perm.append("")
    first = string[0]
    print "first = " + str(first)
    rem = string[1:len(string)]
    print "rem = " + str(rem)
    words = getperm(rem)
    for word in words:
        for i in range(len(word)):
            temp = string[0:i] + first + string[i:len(string)]
            print "temp = " + str(temp)
            perm.append(temp)

    return perm

if __name__=="__main__":
    a = "ab"
    mag  = getperm(a)
    print mag

My expected output would be:

['', 'a', 'b', 'ab']

My actual output is:

[]

Can anyone help me figure out what's going on? Is this some nuance of python, or is there a bug in my code? I think my code should be ok -- I'm going off the fifth edition of Cracking the coding interview

Thank you!

Answer 1

You're overthinking it

This part is trying to do too much

for word in words:
    for i in range(len(word)):
        temp = string[0:i] + first + string[i:len(string)]
        print "temp = " + str(temp)
        perm.append(temp)

See how simple it really should be

def get_powerset (string):
    perm = []
    if len(string) == 0:
        perm.append("")
        return perm
    #if len(string) == 1:
    #   perm.append(string)
    #   perm.append("")
    first = string[0]
    print "first = " + str(first)
    rem = string[1:len(string)]
    print "rem = " + str(rem)
    words = get_powerset(rem)
    perm.extend(words)
    for word in words:
        perm.append(first+word)

    return perm

if __name__=="__main__":
    a = "ab"
    mag  = get_powerset(a)
    print mag

Now you should be able to make the code look a lot nicer with a little refactoring

Answer 2

Is this what you want?

import itertools as it

def func(s):
    for i in range(len(s)+1):
        for combo in it.combinations(s,i):
            yield "".join(combo)

print list(func("abc"))

Answer 3

Here's a refactored iterative solution without the itertools module:

def powerset(s):
    a = ['']
    for i,c in enumerate(s):
        for k in range(2**i):
            a.append(a[k]+c)
    return a

Answer 4

There are a method for permutations:

>>> import itertools
>>> chars = "ABCD"
>>> perms = list(itertools.permutations(chars))
>>> print(perms)
[('A', 'B', 'C'),
 ('A', 'C', 'B'),
 ('B', 'A', 'C'),
 ('B', 'C', 'A'),
 ('C', 'A', 'B'),
 ('C', 'B', 'A')]

Answer 5

Have you tried tracing through what your algorithm actually does?

getperm('ab'):
  first, rem = 'a', 'b'
  words = getperm('b')
    first, rem = 'b', ''
    words = getperm('')
    words = ['']
    for word in words:
      for i in range(len(word)):
        pass # only called on '', so doesn't matter
    return []
  words = []
  for word in words:
    pass # only called on [], so doesn't matter

So, there's no nuance of Python here; your algorithm returns the empty list in O(N) steps, and you've coded that algorithm properly in Python.

(Instead of tracing it by hand, of course, you can add some more useful print statements and see what each step is actually doing.)

It probably wasn't the algorithm you wanted, but you'll need to tell us what you were trying to do. Are you, e.g., porting some pseudocode from Hoare into Python? If so, what's the pseudocode?

Answer 6

Use powerset from more_itertools:

>>> import more_itertools

>>> ["".join(p) for p in list(more_itertools.powerset("ab"))]
['', 'a', 'b', 'ab']

This powerset is a convenience function directly implemented from the itertools recipes.