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!

Ectomere

You're looking to generate the power set, not permutations. The only permutations of the string 'ab' are 'ab' and 'ba'. – Cristobalcristobalite

Also, you really shouldn't name a string string (that's the name of a built-in module), and I'm not sure what you're trying to accomplish by calling str on objects that are already strings (first, rem, etc.). – Zionism

@Matt Ball Yes -- good call. Even so, I'm not generating 'ab' or 'ba'. Do you know why? – Ectomere

@Zionism Very true -- I renamed string to something different, and removed the redundant str() but am still receiving the errors. Any idea why? – Ectomere

Well, obviously those weren't causing your problems; they were just making it harder to read… Meanwhile, you should update the question with the edited version of the code. – Zionism

I changed the title of the question, since the output you are expecting is the powerset. permutations means something different – Culpa

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

Culpa

That did it! Thank you. What does extend do that my code wasn't doing? – Ectomere

@mythander889, .extend just loads the result of the previous level into the current result. – Culpa

I tried running this code, it does not print the powers, it just prints all the alphabets of a string. – Effusive

@nakulchawla09, I'm not sure what you mean by "powers", but it is probably different to a powerset – Culpa

I am sorry for the typing mistake, I meant power set only. For this program I was somehow getting the output [" ", "a", "b"] , I was thinking on the terms of getting an output like [" ", "a", "b", "ab", "ba"] – Effusive

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"))

Carapace

I believe that would do it, but I'm looking to implement the solution using recursion. Thank you! – Ectomere

was searching for combinations with replacement. Saw this, went to docs.. combinations_with_replacement() -- actually a method there! :') – Ane

Is there a way to do what you do without using the package itertools? – Effusive

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

Retread

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

Gore

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?

Zionism

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.

Urease