9文字のすべての順列を見つける

Question

私はこの機能に少し問題があります。

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分以内）であるかどうか疑問に思います。

Answer 1

あなたの現在のランタイムの複雑さは、文字から生成された各単語について、辞書全体を線形時間で調べて見つけようとすることです。これは、辞書のサイズが大きくなるにつれて、実際には遅くなります。したがって、複雑さはO(K * D)です。ここで、Kは生成されたサブセットの数です。Dは辞書のサイズです。

あなたが最適化できることの1つは、辞書内の単語を検索することです。あなたはPython setで辞書を保存することができます。これは、任意の要素に対して一定の時間検索をサポートします。これにより、複雑さが改善され、セットの作成にはO(D)、単語のチェックにはO(K)となります。これは全体的にO(D + K)の複雑さにつながり、O(D * K)よりはるかに優れており、おそらく数分ではなく数秒で実行されます。