优化一种查找字符串的所有排列的方法

Question

我解决了一个难题，但需要优化我的解决方案。难题说我要取一个字符串S，查找其字符的所有排列，对结果进行排序，然后返回该列表中出现的其中一个基于索引的索引号S。

例如，字符串'bac'出现在其排列列表中的第3个位置：['abc', 'acb', 'bac', 'bca', 'cab', 'cba']。

我的问题是，谜题限制我的执行时间为500毫秒。其中一个测试用例通过“BOOKKEEPER”作为输入，需要4.2秒才能完成。

我采用了一种（可能是天真的）动态编程方法，使用memoization，使用一个由特定字符集的特定排列组成的字典，但这还不够。

我的瓶颈是什么？

我正在分析，看看我能否回答我自己的问题，但我邀请那些直接看到问题的人帮助我理解我是如何减缓这种情况的。

编辑：我的解决方案似乎超过itertools.permutations。 10秒以上输入“问题”。但公平地说，这包括时间打印，所以这可能不是一个公平的比较。即便如此，我宁愿提交具有竞争力表现的手写解决方案，以了解为什么我的选择不如选择模块。

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') 

Answer 1

提供我自己的答案，假设优化代码的好方法是首先不使用它。由于我强烈地强调了如何加快我发布的代码的速度，所以我鼓励其他人改善这一点。

@Evert发布​​的评论：

我想你能拿出一个公式来计算输入字的位置的基础上，字母排序（因为列表是按字母顺序排序）的这些信。如果我正确理解这个难题，它只会要求返回输入的位置，而不是所有的排列。所以你要抓住一些笔和纸，并找出这个问题的表述。

按照这种推理，从其他类似的建议中，我想更多的计数组合基于一种方法：

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 < firstletter]) 
    startIndex = sum([permutations(omit(s, s.index(c))) for c in predecessors]) 

    return startIndex + listPosition(s[1:]) 

这产生正确的输出，在高速通过拼图（业绩指标不记录，但明显不同）。实际上并未产生单个字符串排列。

以一个例子输入QUESTION：

我们知道，无论出现在列表中的“问题”，它将以“Q”之前来字母开头的所有排列后出现。同样可以说是子线下的线。

我找到firstletter = 'Q'之前的字母，它存储在predecessors。 set可防止对重复字母的输入进行重复计数。

然后，我们假设predecessors中的每个字母都充当前缀。如果我从字符串中省略前缀并查找其余字母的排列总和，则我们发现在初始输入的第一个字母之前必须出现的排列数。递归，然后对结果进行求和，最终得到开始位置。

Answer 2

您的瓶颈在于N项列表的排列数为N！ （N因子）。随着输入量的增加，这个数字会非常快速地增长。

您可以做的第一个优化是您不必存储所有排列。这是一个递归解决方案，可以生成已排序的所有排列。 “诀窍”是在生成排列之前对单词的字母进行排序。

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) > 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) > 1 else "", 
    ",".join(["%d" % i for i in results]) 
) 
    print "" 


if __name__ == '__main__': 
    puzzle("ABC")  

但是，当输入较大时，该程序需要很长时间才能运行。在我的计算机（2.5 GHz英特尔核i5）

• 输入= “ABC”（3个字符）：0.03秒
• 输入= “问题”（8位）：0.329秒
• 输入=“的问题“（9个字符）：2.848秒
• 输入=‘会计’（10个字符）：30.47秒

到的唯一方法‘的时钟节拍’是要弄清楚的方式来计算所述串的位置没有生成所有的排列。

查看上面Evert的评论。

N.B.当输入包含重复的字母时，初始字符串会在多个位置出现。我假设你只需要报告第一次发生。

Answer 3

我相信答案是不会产生所有的排列或排序。让我们保持它的简单，看看它是如何比较的性能代价：

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')) 

的时间设置（单位：秒）

  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 

从科学PROG的代码的输出不产生与其他两个一致的答案因为它产生了更大的指数和多个指数，所以我没有包括它的时间长度。