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:

&gt;&gt;&gt; from itertools import permutations
&gt;&gt;&gt; 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:

&gt;&gt;&gt; permute('&lt;&gt;')
['&lt;&gt;', '&lt;&gt;', '&lt;&gt;', '&lt;&gt;']


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.


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.

    &gt;&gt;&gt; capitalizations('abc')
    ['ABC', 'ABc', 'AbC', 'Abc', 'aBC', 'aBc', 'abC', 'abc']
    &gt;&gt;&gt; capitalizations('')
    ['']
    &gt;&gt;&gt; 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))))