查找9个字符的所有排列
查找9个字符的所有排列
提问于 2017-02-13 06:58:19
我对这个函数有一点小问题。
def check_possible(input):
possibilities = []
solutions = []
dict = dictionary(input)
dict.get_dict()
words = dict.get_all_words()
for L in range(0, len(input)+1):
for subset in itertools.permutations(input, L):
possibilities.append(subset)
for possibility in possibilities:
poss = "".join(possibility)
if len(poss) > 3 and len(poss) < 9:
for item in words:
for i in item:
if poss in i:
solutions.append(poss)
return solutions基本上，它接受一个包含9个字符的列表作为参数，并生成一个包含3到9个字符且在字典中的所有可用排列的列表(使用26个字典文件，每个字母1个，为列表中给出的每个字母创建一个子列表，然后检查由上述函数生成的每个排列)。
所以这个函数应该会返回：
>>input = ['a', 'b', 'd', 'c', 'e', 'b', 'd', 'e', 'f']
<<['dace', ..., 'face', 'decaf', 'bedad', 'ceded', 'faded', 'faced', 'beaded', 'deface', 'decade', 'defaced']虽然这是有效的，并且它返回正确的值，但它需要10 - 15分钟才能完成。我想知道是否有一种方法可以在更短的时间内(最好是在一分钟内)获得相同的结果。
回答 1
Stack Overflow用户
发布于 2017-02-13 07:26:35
您当前的运行时复杂性是，对于从字母生成的每个单词，您在线性时间内检查整个字典以尝试找到它。随着字典大小的增加，这会变得非常慢。所以复杂度是O(K * D)，其中K是生成的子集的数量，D是字典的大小。
您可以优化的一件事是在字典中查找单词。您可以将字典保存在python set中，它支持对任何元素进行恒定时间查找。这提高了构造集合的O(D)和检查单词的O(K)的复杂性。这导致了总体上O(D + K)的复杂性，这比O(D * K)要好得多，可能会在几秒钟而不是几分钟内运行。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/42194268
复制相关文章
相似问题
腾讯云开发者
