查找9个字符的所有排列

我遇到这个函数有点问题。查找9个字符的所有排列

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分钟才能完成。我想知道是否有办法达到相同的结果，但时间较短（最好在一分钟之内）。

来源

2017-02-12 Notgivinit

当不在函数内部时，返回值是什么？ –

我的歉意，它应该是在一个函数。 – Notgivinit

也许[itertools.permutations（）]（https://docs.python.org/2/library/itertools.html#itertools.permutations）可以为您完成这项工作。干！ –

您当前的运行时复杂度是，对于字母中的每个生成的单词，都会在线性时间内检查整个字典以尝试找到它。随着字典大小的增长，这会变得非常慢。所以你的复杂度是O(K * D)，其中K是生成的子集的数量，而D是字典的大小。

你可以优化的一件事是查找字典中的单词。您可以将该字典保存在Python中set，它支持任何元素的恒定时间查找。这样可以将您的复杂性提高到O(D)用于构建集合，并且O(K)用于检查单词。这总体上导致O(D + K)的复杂度，这比O(D * K)好得多，并且可能在数秒内而不是在几分钟内运行。

来源

2017-02-12 23:26:34

它需要15分钟来产生字符的排列，比较部分是相对较快（一对夫妇秒）。我希望我能正确理解你的答案。 – Notgivinit

这看起来不对。排列的数量是（9！+ 8！+ 7！+ ..），这些都是大约500k，并且应该在几秒钟内生成。事实上，我试过你的第一个循环，它在我的机器上只运行一秒钟。 –

是的，我很抱歉，我现在看到了我的错误。明天我会重做这个函数来使用set。我应该使用任何特殊的比较方法，使其更快或只是简单的“排列项目：如果在dictionarySet项目：打印（项目）”？我很抱歉，我仍然是初学者，所以我只是想学习。 – Notgivinit

查找9个字符的所有排列

回答

相关问题