我解决了一个难题，但需要优化我的解决方案。谜题说我要获取一个字符串 S，找到它的字符的所有排列，对我的结果进行排序，然后返回 S 出现位置的从一开始的索引那个 list 。
例如，字符串 'bac' 出现在其自身排列的排序列表中的第 3 个位置:['abc', 'acb', 'bac', 'bca', 'cab', ' cba'].
我的问题是拼图将我的执行时间限制为 500 毫秒。其中一个测试用例通过了“BOOKKEEPER”作为输入，我需要大约 4.2 秒才能完成。
我采用了一种(可能是幼稚的)动态编程方法，使用由某些字符集的一个特定排列键入的字典进行内存，但这还不够。
我的瓶颈是什么？
同时我正在分析以查看是否可以回答我自己的问题，但我邀请那些直接看到问题的人帮助我理解我是如何放慢速度的。
编辑:我的解决方案似乎优于 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')
请您参考如下方法:
在假设优化代码的好方法是首先不使用它的前提下，提供我自己的答案。由于我强烈强调确定加快我发布的代码速度的方法，因此我支持其他所有人在这方面做出的改进。
@Evert 发表了以下评论:
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.
根据这个推理，在其他人的类似建议中，我尝试了一种更多基于枚举组合的方法:
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为例:
我们知道，“QUESTION”出现在列表中的任何位置，它都会出现在以“Q”之前的字母开头的所有排列之后。子字符串也可以这样说。
我找到了 firSTLetter = 'Q' 之前的字母，这些字母存储在 predecessors 中。 set 防止重复输入字母的重复计数。
然后，我们假设 predecessors 中的每个字母都充当前缀。如果我从字符串中省略该前缀并找到剩余字母的排列总和，我们就会找到必须出现在初始输入的第一个字母之前的排列数。递归，然后对结果求和，最后得到起始位置。
