Python で幅優先検索アルゴリズムを使用して、3 文字の単語から別の単語への最短の「パス」を見つけています。私はそれを機能させましたが、パフォーマンスはひどいものであり、私の単語の子世代機能を疑っています.
基本的に、キューからポップするすべての単語に対して、1 文字を交換して形成できる他のすべての 3 文字の単語を生成します。関数は次のように機能します。
#Pseudo code
For each position (1-3)
For each letter (a-z)
create a new word by exchanging the letter at the position
if this word is a valid word and is not used earlier
add it to the return list
return the list
通常、これには約 0.03 秒かかります。これを行うより速い方法はありますか？
有効な単語のリストがあり、実際には単一のパスを探しているのではなく (なぜそれを最適化する必要があるのか)、多くのパスを探していると仮定します。これはnetworkXで非常に簡単に行うことができます:
from networkx import Graph
from networkx.algorithms.shortest_paths import shortest_path, all_pairs_shortest_path
from itertools import combinations
WORDS = {'cat', 'hat', 'sat', 'car', 'cad', 'had', 'pad', 'pat', 'can', 'man'}
def makeGraph(words):
""" create a graph where nodes are words and two words are
connected iff they have one different letter """
G = Graph()
# all word combinations
for a,b in combinations(WORDS,2):
# number of different letters
diff = sum(1 for x,y in zip(a,b) if x!=y)
if diff == 1:
G.add_edge(a,b)
return G
g = makeGraph(WORDS)
# path between two words
print shortest_path(g, 'cat', 'pad')
# generating all shortest paths is way more efficient if you want many paths
paths = all_pairs_shortest_path(g)
print paths['cat']['pad']
例の言葉をくれた@Ducanに感謝します。
これらのアルゴリズムを自分で実装したい場合は、wikipediaで多くの説明を見つけることができます。古典的な単一ソースの最短パス アルゴリズムはDijkstra のものであり、古典的なすべてのペアの最短パス アルゴリズムはFloyd-Warshallです。
車輪を再発明したい場合は、おそらくこれが役立ちます（NBこれはリテラルを設定しているため、少なくともPython 2.7が必要です）：
from collections import defaultdict
WORDS = {'cat', 'hat', 'sat', 'car', 'cad', 'had', 'pad', 'pat', 'can', 'man'}
D1 = defaultdict(set)
D2 = defaultdict(set)
D3 = defaultdict(set)
for w in WORDS:
D1[w[:2]].add(w)
D2[w[0]+w[2]].add(w)
D3[w[1:]].add(w)
def follows(w):
followers = set(D1.get(w[:2]).union(D2.get(w[0]+w[2]), D3.get(w[1:])))
followers.discard(w)
return followers
for w in WORDS:
print(w, follows(w))
おそらく次善の方法で車輪を再発明する代わりに、既存のモジュールを使用します。