Optimizing a way to find all permutations of a string
<p>I solved a puzzle but need to optimize my solution. The puzzle says that I am to take a string <em>S</em>, find all permutations of its characters, sort  my results, and then return the one-based index of where <em>S</em> appears in that list.</p>

<p>For example, the string 'bac' appears in the 3rd position in the sorted list of its own permutations: <code>['abc', 'acb', 'bac', 'bca', 'cab', 'cba']</code>.</p>

<p>My problem is that the puzzle limits my execution time to 500ms. One of the test cases passed "BOOKKEEPER" as an input, which takes ~4.2s for me to complete.</p>

<p>I took a (possibly naive) dynamic programming approach using memoization using a dict keyed by one particular permutation of some character set, but that's not enough.</p>

<p><strong>What is my bottleneck?</strong></p>

<p>I'm profiling in the meantime to see if I can answer my own question, but I invite those who see the problem outright to help me understand how I slowed this down.</p>

<p><strong>EDIT:</strong> My solution appears to outperform <code>itertools.permutations</code>. 10+ seconds for input "QUESTION". But to be fair, this includes time printing so this might not be a fair comparison. Even so, I'd rather submit a handcoded solution with competitive performance knowing why mine was worse than to opt for a module.</p>

<pre><code>memo = {}

def hash(word):
    return ''.join(sorted(word))

def memoize(word, perms):
    memo[hash(word)] = perms
    return perms

def permutations(word, prefix = None):
    """Return list of all possible permutatons of given characters"""
    H = hash(word)

    if H in memo:
        return [s if prefix is None else prefix + s for s in memo[H]]

    L = len(word)

    if L == 1:
        return [word] if prefix is None else [prefix + word]

    elif L == 2:
        a = word[0] + word[1]
        b = word[1] + word[0]

        memoize(word, [a, b])

        if prefix is not None:
            a = prefix + a
            b = prefix + b

        return [a, b]

    perms = []
    for i in range(len(word)):
        perms = perms + permutations(word[:i] + word[i+1:], word[i])

    memoize(word, perms)

    return [prefix + s for s in perms] if prefix is not None else perms


def listPosition(word):
  """Return the anagram list position of the word"""
  return sorted(list(set(permutations(word)))).index(word) + 1

print listPosition('AANZ')
</code></pre>

<p>Providing my own answer under the assumption that a good way to optimize code is to not use it in the first place. Since I strongly emphasized identifying ways to speed up the code I posted, I'm upvoting everyone else for having made improvements in that light.</p>

<p>@Evert posted the following comment:</p>

<blockquote>
  <p>I would think you can come up with a formula to calculate the position of the input word, based on the alphabetic ordering (since the list is sorted alphabetically) of the letters. If I understand the puzzle correctly, it only asks to return the position of the input, not all of the permutations. So you'll want to grab some pen and paper and find a formulation of that problem. </p>
</blockquote>

<p>Following this reasoning, among similar suggestions from others, I tried an approach based more in enumerative combinatorics:</p>

<pre><code>from math import factorial as F
from operator import mul

def permutations(s):
    return F(len(s)) / reduce(mul, [F(s.count(c)) for c in set(s)], 1)

def omit(s,index):
    return s[:index] + s[index+1:]

def listPosition(s):
    if (len(s) == 1):
        return 1

    firstletter = s[0]
    predecessors = set([c for c in s[1:] if c &lt; firstletter])
    startIndex = sum([permutations(omit(s, s.index(c))) for c in predecessors])

    return startIndex + listPosition(s[1:])
</code></pre>

<p>This produced correct output and passed the puzzle at high speed (performance metrics not recorded, but noticably different). Not a single string permutation was actually produced.</p>

<p>Take as an example input <code>QUESTION</code>:</p>

<p>We know that wherever in the list "QUESTION" appears, it will appear after all permutations that start with letters that come before "Q". The same can be said of substrings down the line.</p>

<p>I find the letters that come before <code>firstletter = 'Q'</code>, which is stored in <code>predecessors</code>. The <code>set</code> prevents double counting for input with repeated letters.</p>

<p>Then, we assume that each letter in <code>predecessors</code> acts as a prefix. If I omit that prefix from the string and find the sum of permutations of the remaining letters, we find the number of permutations that <em>must appear</em> before the initial input's <em>first letter</em>. Recurse, then sum the results, and you end up with the start position.</p>

python optimization