строка проверки python содержит все символы

Question

Я читаю длинный список слов, и я создал узел для каждого слова в списке. Каждый узел имеет атрибут «слово» для своей позиции в списке.

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

Я также алфавитном порядке каждое слово на символ, так что CAT -> ACT

Я хочу нарисовать край от каждого уникального начального слова, ко всем возможным цепям, чтобы я мог видеть все возможные цепочки в списке.

Например

A -> AN -> TAN -> RANT

Однако --x-> T

Это моя попытка

for i in range(0, G.number_of_nodes()-1): 

    if (((len(G.node[i]['word'])+1) == len(G.node[i+1]['word']))  and (G.node[i]['word'] in G.node[i+1]['word'])): 
     print G.node[i]['word'], G.node[i+1]['word'] 

Дал мне это ,

 
DGO DGOS 
DGOS DGOSS 
I IN 
ELLMS ELLMSS 
AEPRS AEPRSS 
INW DINW 
DINW DINWY 

What the word list and the alphabetical list looks like

Почему я не вижу IN INW?

Кроме того, AGNRT AGNRST должен быть там, но я не понимаю, почему, наряду с множеством других пар

Как вы думаете, я не так?

Answer 1

Вы, кажется, сравнивая каждый узел только с одним другим узлом, так

«IN» непосредственно следует «Я» в вашем словника, но «INW» не сразу после того, как «IN»

Answer 2

ВЫГЛЯДИТ как проблема формальных языков. Как вы обрабатываете узлы зацикливания?

IN INW в списке, который вы указали.

AGNRT AGNRST не в списке, потому что вы начали с одной буквы, что письмо должно быть в следующем слове, например, я -> IN, но не в AGNRT или AGNRST

Answer 3

проблема в том, что вы сравниваете только слова, которые появляются рядом друг с другом в списке, то есть слова i и i+1, например I и IN находятся рядом друг с другом, как и WIN и WIND, но IN и WIND находятся далеко друг от друга. Кажется, вы хотите сравнить все возможные слова, требующие более сложного алгоритма. Вот идея:

1. Сделайте словарь, в котором эти ключи отсортированы, а значения - это списки фактических слов, например. {"ACT": ["CAT", "ACT", "TAC], ...}. A collections.defaultdict(list) будет полезен для этого.
2. Сортировка полного списка слов по длине. Вы можете использовать list.sort(key=len), если у вас есть только список слов.
3. Итерации по списку отсортированы по длине. Для каждого слова пройдите все подмножества длины n-1.Что-то вроде for i in range(len(word)): process(word[:i] + word[i+1:]). Вы можете быть осторожны с дубликатами здесь.
4. Для каждого подмножества сортируйте подмножество и найдите его в словаре. Создайте ссылку на каждое слово в значении словаря (список фактических слов) на большее слово.

Answer 4

Вы можете использовать стороннюю библиотеку python, python-levenshtein, для вычисления Levenshtein Distance, который является расстоянием редактирования строки. В вашем случае единственным разрешенным «редактированием» является «вставка» символа в следующую строку/слово в вашем списке, поэтому вам также нужно будет проверить, что длина следующего слова равна 1 плюс предыдущее слово.

Вот пример кода, который позволит достичь наш материал:

import Levenshtein as lvst 

if len(word2) - len(word1) == 1 and lvst.distance(word1, word2) == 1: 
    print(word1, word2) 

Вы можете установить python-levenshtein либо apt-get (общесистемного) или pip:

sudo apt-get install python-levenshtein

или

sudo apt-get install python3-levenshtein

или

pip install python-levenshtein