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>Your bottleneck resides in the fact that the number of permutations of a list of N items is N! (N factorial).  This number grows very fast as the input increases.</p>

<p>The first optimisation you can do is that you do not have to store all the permutations.  Here is a recursive solution that produces all the permutations already sorted.  The "trick" is to sort the letters of the word before generating the permutations.</p>

<pre><code>def permutations_sorted( list_chars ):
  if len(list_chars) == 1:  # only one permutation for a 1-character string     
    yield list_chars
  elif len(list_chars) &gt; 1:
    list_chars.sort()
    for i in range(len(list_chars)):
      # use each character as first position (i=index)                          
      head_char = None
      tail_list = []
      for j,c in enumerate(list_chars):
        if i==j:
          head_char = c
        else:
          tail_list.append(c)
      # recursive call, find all permutations of remaining                      
      for tail_perm in permutations_sorted(tail_list):
        yield [ head_char ] + tail_perm

def puzzle( s ):
  print "puzzle %s" % s
  results = []
  for i,p_list in enumerate(permutations_sorted(list(s))):
    p_str = "".join(p_list)
    if p_str == s:
      results.append( i+1 )
  print "string %s was seen at position%s %s" % (
    s,
    "s" if len(results) &gt; 1 else "",
    ",".join(["%d" % i for i in results])
  )
  print ""


if __name__ == '__main__':
  puzzle("ABC")       
</code></pre>

<p>Still, that program takes a long time to run when the input is large.  On my computer (2.5 GHz Intel core i5)</p>

<ul>
<li>Input = "ABC" (3 characters): 0.03 seconds</li>
<li>Input = "QUESTION" (8 characters): 0.329 seconds</li>
<li>Input = "QUESTIONS" (9 characters): 2.848 seconds</li>
<li>Input = "BOOKKEEPER" (10 characters): 30.47 seconds</li>
</ul>

<p>The only way to "beat the clock" is to figure a way to compute the position of the string <strong>without</strong> generating all the permutations.</p>

<p>See the comment by Evert above.</p>

<p>N.B. When the input contains letters that are repeated, the initial string is seen at more than one place.  I assume you have to report only the first occurence.</p>

python optimization