путь в графе слов

Question

График Word $W_n$ - граф, множество вершин которого состоит из всех $n$-буквенные английские слова, множество ребер которых состоит из всех вершин, различающихся ровно на одну букву в одной позиции. Например, в$W_4, \{hard, card\}$это край. Найдите путь от неправильного к правильному$W_5.$

Должен быть способ сместить r в неправильном месте влево, хотя я не уверен, как это сделать. Слово рядом с неправильным, которое может быть полезно, включает wring. Путь от выкручивания к цене будет таким: выжать, принести, рассол, невеста, гордость, цена, приз, проза, лежать, дрон. Однако это не кажется очень полезным.

Answer 1

Я не совсем уверен, что вы выбрали правильные теги, или даже не обязательно, что это должно быть математически, но у меня есть для вас ответ. Слова в ответе довольно необычны, но поиск в Google показал мне, что это действительно слова. Позже я попытаюсь сделать то же самое, используя только более общие слова, и посмотрю, смогу ли я найти более «настоящий» ответ. В любом случае, вот вам:

wrong
wrung
drung
drunt
daunt
dasnt
dasht
hasht
hacht
hicht
richt
right

Изменить: Используя только слова в словаре Scrabble , мы имеем:

wrong
prong
prone
phone
phons
pions
lions
linns
lines
sines
sinhs
sighs
sight
right

Я добился этого с помощью следующей программы на Python, которая использует алгоритм Дейкстры:

from dijkstra import Graph, DijkstraSPF
from tqdm import tqdm

def load_words():
    with open('words_alpha.txt') as word_file:
        valid_words = set(word_file.read().split())

    return valid_words

def d(word1,word2):
    t = 0
    for i in range(len(word1)):
        if word1[i] != word2[i]:
            t += 1
    return t

def near(word):
    s = set()
    for w in w5:
        if d(w,word) == 1:
            s.add(w)
    return s

w = load_words()
w5 = set([word if len(word) == 5 else '' for word in w])
w5.remove('')
w5 = list(w5)

w5g = Graph()

for i in tqdm(range(len(w5)), "Building Graph"):
    for n in near(w5[i]):
        w5g.add_edge(w5[i],n,1)

d = DijkstraSPF(w5g, "wrong")
print("\n".join(d.get_path("right")))

Если вы хотите использовать описанное выше для решения подобных проблем, вам необходимо установить пакеты. Команды для этого различаются в зависимости от вашей ОС и установки Python, но в целом они выглядят следующим образом:

$ pip3 install tqdm $ pip3 install dijkstra

Я собрал это по кусочкам из пары мест, так что, вероятно, это не так изящно, как могло бы быть - это определенно не так быстро, как могло бы быть.

Словари слов, которые я использовал, можно найти здесь и здесь .