3
\$\begingroup\$

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 )
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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))))
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Morwenn Jun 2 '15 at 16:05
  • \$\begingroup\$ 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. \$\endgroup\$ – otto Jun 2 '15 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.