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>I believe the answer is to not produce all the permutations nor sort them.  Let's keep it simple and see how it compares performance-wise:</p>

<pre><code>import itertools

def listPosition(string):
    seen = set()

    target = tuple(string)

    count = 1;

    for permutation in itertools.permutations(sorted(string)):
        if permutation == target:
            return count
        if permutation not in seen:
            count += 1
            seen.add(permutation)

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

<p><strong>TIMINGS</strong> (in seconds)</p>

<pre><code>           Sage/Evert  Mine  Sage     Answer
QUESTIONS     0.02     0.18  0.45      98559
BOOKKEEPER    0.03     0.11  2.10      10743
ZYGOTOBLAST   0.03     24.4  117(*)  9914611

(*) includes ~25 second delay between printing of answer and program completion
</code></pre>

<p>The output from Sci Prog's code did not produce answers that agreed with the other two as it produced larger indexes and multiple of them so I didn't include its timings which were lengthy.</p>

python optimization