All upper and lowercase permutations of a string

A couple of questions:

• Is the algorithm wasting CPU time or memory unnecessarily?

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

1. Review

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

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

-
The Python style guide (PEP8) recommends:


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

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

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

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

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

StackExchange Code Review Q#92465, answer score: 4