最初にpythonでの幅 - 計算上の最大？

Question

は、私はPythonで、次の「ゲーム」を実装しようとしています：

開始ワードを考えると、との目標単語を見つける修正 ステップごとの変更許可：削除したり、任意の文字を追加し、

タスクを並べ替えます最短のステップでスタートからゴールまでの道を見つけることです。

私のアプローチは、文字を追加/削除し、結果の文字を置換し、辞書内の各置換文字を検索することでした。

これはすぐに実行時間が長くなります（9文字の単語と最初のステップでは約60秒です）。

ここに私のコードです。

import time 
from itertools import permutations 
startword = 'croissant' 

nodes = list() 

nodes.append(startword) 

dicts = set([line.rstrip('\n') for line in open('wordList.txt')]) 
alpha = set([chr(i) for i in range(ord('a'),ord('z')+1)]) 


def step(nodes): 
    nnodes = list() 
    for word in nodes: 
     for s in word: 
      new_word = word.replace(s, '', 1) 
      perms = [''.join(p) for p in permutations(new_word)] 
      for per in perms: 
       if per in dicts: 
        nnodes.append(per) 
     for s in alpha: 
      new_word = word + s 
      perms = [''.join(p) for p in permutations(new_word)] 
      for per in perms: 
       if per in dicts: 
        nnodes.append(per) 
return set(nnodes) 


btime = time.time() 
step(nodes) 
print time.time() - btime 

どのようにパフォーマンス/ロジックを改善できますか？具体的には、幅広い最初の検索を使用するように求められます。

Answer 1

興味深い質問！パフォーマンスを大幅に向上させる方法があります。単語リストをたどってチェックする代わりに、単語リストの各単語の文字をアルファベット順に並べ替えて、アルファベット順に短縮された/長くされた単語を直接比較することができます。

たとえば、croissantを使用して、文字をアルファベット化してacinorsstを生成することができます。次に、文字が削除または追加されたacinorsstが、キーがアルファベット順のストリングであり、対応する値（アルファベット順に対応する実際の単語のリスト）を検索するリストのdefaultdictにあるかどうかを確認します。

それははるかに少ない混乱コードで説明することであるので、私は以下のことを掲載している：

from collections import defaultdict 
import itertools as its 
import time 

def get_alpha_dicts(): 
    wa_dict = {}#word: alphabetized dict 
    aw_dict = defaultdict(list)#alphabetized: corresponding WORDS dict 
    for line in open('wordList.txt'): 
     word = line.rstrip('\n') 
     alpha_word = ''.join(sorted(word)) 
     wa_dict[word] = alpha_word 
     aw_dict[alpha_word].append(word) 
    return wa_dict, aw_dict  

def step(nodes, aw_dict): 
    alpha = set([chr(i) for i in range(ord('a'),ord('z')+1)]) 
    nnodes = list() 
    for word in nodes: 
     alpha_word = ''.join(sorted(word)) 
     #remove a char from word 
     short_words = set([''.join(w) for w in its.combinations(alpha_word, len(start_word)-1)]) 
     for short_word in short_words: 
      nnodes.extend(aw_dict[short_word]) 
     #add a char to word 
     long_words = [''.join(sorted(alpha_word + s)) for s in alpha] 
     for long_word in long_words: 
      nnodes.extend(aw_dict[long_word]) 
    return set(nnodes) 

if __name__ == "__main__": 
    start_word = 'croissant' 
    nodes = list() 
    nodes.append(start_word) 
    wa_dict, aw_dict = get_alpha_dicts() 
    btime = time.time() 
    print step(nodes, aw_dict) 
    print time.time() - btime 

はそれが役に立てば幸い！