All upper and lowercase permutations of a string

Question

A couple of questions:

1. Is the algorithm wasting CPU time or memory unnecessarily?
2. If there is something in the code that is not idiomatic Python, how to improve on that?

def permute_first( c ):
 retval = []
 retval.append( c.upper() )
 retval.append( c.lower() )
 return retval
def permute( str ):
 leads = permute_first( str[0] )
 remain = str[1:]
 if not remain:
 return leads
 permutations = permute( remain )
 new_permutations = []
 for perm in permutations :
 for lead in leads:
 new_permutations.append( lead + perm ) 
 return new_permutations
og = "Question"
print permute( og )

Answer 1

The base case in your recursion is incorrect: it should be an empty string, not a one-character string.

Extraneous whitespace inside parentheses is explicitly un-Pythonic, by PEP 8.

There is usually a better way to do this pattern, which you used twice:

some_list = []
some_list.append(element)
some_list.append(more_stuff)
return some_list

There is often a one-liner to define the entire list at once, possibly involving a list comprehension. Or, if it's a "long" list, you may want to stream the results as a generator, as I've done below.

def capitalization_permutations(s):
 """Generates the different ways of capitalizing the letters in
 the string s.
 >>> list(capitalization_permutations('abc'))
 ['ABC', 'aBC', 'AbC', 'abC', 'ABc', 'aBc', 'Abc', 'abc']
 >>> list(capitalization_permutations(''))
 ['']
 >>> list(capitalization_permutations('X*Y'))
 ['X*Y', 'x*Y', 'X*y', 'x*y']
 """
 if s == '':
 yield ''
 return
 for rest in capitalization_permutations(s[1:]):
 yield s[0].upper() + rest
 if s[0].upper() != s[0].lower():
 yield s[0].lower() + rest

Answer 2

1. Review

1. "Permutations" is not the right word for what this code does. The permutations of a sequence are the different ways the items can be ordered: for example, the permutations of ABC are ABC, ACB, BAC, BCA, CAB and CBA. These can be computed using the built-in itertools.permutations:

   >>> from itertools import permutations
   >>> list(map(''.join, permutations('ABC')))
   ['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']
   

   What you have here are the different ways to capitalize the letters in a word, so the name ought to be something like capitalizations.

2. There are no docstrings. What do these functions do and how to I call them?

3. The Python style guide (PEP8) recommends:

   Avoid extraneous whitespace ... immediately inside parentheses, brackets or braces.

4. The body of permute_first could be written more simply:

   return [c.upper(), c.lower()]
   

   In fact this is so simple that there's no real need for this to be a separate function at all.

5. If str contains non-letters then we get duplicates in the output:

   >>> permute('<>')
   ['<>', '<>', '<>', '<>']
   

   Use sorted(set((c.upper(), c.lower()))) to de-duplicate the output.

6. If str is the empty string, permute raises IndexError. It should return a list containing the empty string.

2. Revised code

This is a one-liner using itertools.product:

from itertools import product
def capitalizations(s):
 """Return a list of the different ways of capitalizing the letters in
 the string s.
 >>> capitalizations('abc')
 ['ABC', 'ABc', 'AbC', 'Abc', 'aBC', 'aBc', 'abC', 'abc']
 >>> capitalizations('')
 ['']
 >>> capitalizations('X*Y')
 ['X*Y', 'X*y', 'x*Y', 'x*y']
 """
 return list(map(''.join, product(*(sorted(set((c.upper(), c.lower())))
 for c in s))))

• Morwenn: Just an additional note about permutations: it would be good to add that "permutation" can refer to index-based permutations (e.g. itertools.permutations) as well as to value-based permutations (e.g. std::next_permutation) which are somehow different beasts under a same name.
• otto: Good point on naming, I'll change it to something more suitable. I made permute_first a function since I experimented with other substitions as well, like i and l to 1, but simplified it for the sake of this submission. I wrote this because I want to list all possible written forms of any base word irregardless of capitalization, and it's easy to expand that function to cover l33t speak as well.