-1

つまり、これは私がPythonで書いた最初のプログラムの1つです。文字列を取得して、実際の単語であるすべての文字列を出力しようとしています。完了しましたが（より多くの単語を含む参照ファイルを見つける必要があります）、Pythonが何かを返すのに非常に長い時間がかかると、8文字を超える文字を入力できないため、スケーラブルではありません。

def lower_and_remove_spaces(fill_string):
    '''
    function takes a string of 2 or more characters and prints out all the permutations
    of words that the characters can make. 
    '''
    lower_string = ''

    for i in fill_string:
        if i.isalpha():
            lower_string += i.lower()

    return lower_string    

def fill_list(input_string):
   iter_list = []
   string_list = []
   this_string = lower_and_remove_spaces(input_string)
   for num in range(2,len(this_string)+1):
      iter_list.append(itertools.permutations(this_string,num))

   for iters in iter_list:
      for lists in iters:
         string_list.append(list(lists))

    return string_list

def word_list(string):
   string_list = fill_list(string)
   a_word_list = []
   a_string = ''
   for i in string_list:
      if not a_string == '':
         a_word_list.append(a_string)
      a_string = ''
      for y in i:
         a_string += y
    return a_word_list

私はこれがたくさん飛び回ることを理解していますが、スケーラブルにするためにこれを行うためのより良い方法は何でしょうか？

4

1 に答える 1

5

いくつかの簡単なアイデア：すべての順列を作成することはO（n！）になりますが、これを回避する方法はありません。コードを最適化しても、nがより大きな数に近づくと、壁にぶつかります。有効な単語の辞書がある場合、この問題は少し異なります。病理学的入力セット（辞書にはすべての順列が含まれています）では、これ以上のことはできません。

ただし、次のことができます

  1. 有効な単語の辞書をプレフィックスツリーに保持する
  2. itertools.ieを使用する代わりに、手動で順列を再帰的に生成します。文字を選択し、単語を開始し、再帰します。
  3. 各ステップで、プレフィックスが有効かどうかを確認し、有効でない場合は検索ツリーを削除します。

これのパフォーマンスは、実際にはO（n！）よりもはるかに優れています。

プレフィックスツリーに慣れていない場合は、Pythonハッシュを使用して同じことをシミュレートする方法を次に示します。

   def prefix_hash(list_o_words):
       ret = {}
       for word in list_o_words:
           for i in range(2,len(word)-1):
               ret[word[:i]] = 'prefix'  # this should check if it's a word first..
       ret[word] = 'word'

さらにヘルプが必要な場合は質問してください。

于 2012-08-13T03:52:36.293 に答える