All upper and lowercase permutations of a string

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 ):
remain = str[1:]
if not remain:
permutations = permute( remain )
new_permutations = []
for perm in permutations :
return new_permutations

og = "Question"
print permute( og )


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


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

• 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. Commented Jun 2, 2015 at 16:05
• 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.
– otto
Commented Jun 2, 2015 at 17:30