Сравнение последовательности букв со списком слов в python

#python

#python

Вопрос:

У меня есть список букв, который находится в определенном порядке (подумайте о текстовых сообщениях старой школы, поэтому моя последовательность кнопок здесь равна 4266532)

 letters = [['g', 'h', 'i'], ['a', 'b', 'c'], ['m', 'n', 'o'], ['m', 'n', 'o'], ['j', 'k', 'l'], ['d', 'e', 'f']]
  

и список слов

 words = ['i', 'am', 'an', 'old', 'man']
  

Я хочу посмотреть, сколько совпадающих предложений для этой последовательности букв по сравнению с этим списком слов.

Например, последовательность букв может быть равна «я старый» или «я старый»

РЕДАКТИРОВАТЬ: чтобы уточнить, что я подразумеваю под последовательностью

на старых телефонах, которые все еще имеют кнопки вместо сенсорного экрана. к каждой кнопке (или номеру) прикреплены буквы. Например, к номеру / кнопке «2» ['a','b','c'] прикреплены буквы. К номеру / кнопке «3» ['d,'e','f'] прикреплены буквы. Итак, в моем letters списке выше показано, какие буквы могут появиться на экране при нажатии 4266532

Комментарии:

1. Вы могли бы довольно легко применить грубую силу, насколько велики данные? Также вы не указали логику того, что считается последовательностью. Старик и учитывая, что вы считаете 'i an old' даже an man действительным?

2. это для университетского задания, поэтому данные не будут намного больше, чем я показываю, они могут тестироваться на разных списках слов и последовательностях букв, но размер будет похож @PadraicCunningham

3. Будут ли результаты всегда в порядке, т. Е. Из вашего words объекта?

4. Ну, отсортируйте подсписки и, по крайней мере, тогда вы сможете замкнуть. Могут ли какие-либо слова использоваться вместе?

5. да, они будут в порядке @enderland, и буквы можно использовать только один раз. Итак, если я перебираю буквы, я могу взять только одну букву из каждого подсписка, чтобы помочь в формировании слова

Ответ №1:

Не уверен, каковы ваши полные критерии, но поскольку ваши списки будут небольшими, вы можете сделать что-то вроде:

 from collections import Counter
from itertools import combinations, chain
letters = [['g', 'h', 'i'], ['a', 'b', 'c'], ['m', 'n', 'o'],['m', 'n', 'o'], ['j', 'k', 'l'], ['d', 'e', 'f']]
allowed = set(chain.from_iterable(letters))
words = ['i', 'am', 'an', 'old', 'man']

for phrase in combinations(words, 3):
    phrase_c = Counter(chain.from_iterable(phrase))
    if any((v > 1 and k not in "mno") or k not in allowed for k, v in phrase_c.items()):
        continue
    print(phrase)
  

Что даст вам:

 ('i', 'am', 'old')
('i', 'an', 'old')
('i', 'old', 'man')
  

Если слова всегда являются подмножеством буквы, вы можете удалить if k not in "mno"

если вам нужно быть в порядке, тогда это проще, просто убедитесь, что каждая буква из фразы отображается в подмножествах и в правильном порядке:

 from collections import Counter
from itertools import combinations, chain

letters = [['g', 'h', 'i'], ['a', 'b', 'c'], ['m', 'n', 'o'], ['m', 'n', 'o'], ['j', 'k', 'l'], ['d', 'e', 'f']]

words = ['i', 'am', 'an', 'old', 'man']

for phrase in combinations(words, 3):
    for ind, letter in enumerate(chain.from_iterable(phrase)):
         if ind >= len(letters) or letter not in letters[ind]:
            break
    else:
        print(phrase)
  

Что даст вам:

 ('i', 'am', 'old')
('i', 'an', 'old')
  

Если вы сортируете слова на основе порядка букв и фильтруете слова, которые не содержат букв из набора, вы можете немного уменьшить сложность. Вы также можете учитывать тот факт, что вы можете создавать не более фраз, состоящих из 6 букв, т.е 4266532

Комментарии:

1. хорошо, это поставит меня на правильный путь, хотя (‘i’, ‘old’, ‘man’) не должно быть выводом, потому что его нет в последовательности букв 426653. Также я никогда не видел «коллекции» или «itertools», поэтому мне нужно будет ознакомиться с ними, но спасибо вам за это, по крайней мере, это шаг в правильном направлении

2. Значит, это должно быть в том же порядке?

3. Да, возможно, изображение выше объяснит это лучше, чем у меня

4. означает ли, что комбинации (слова, 3) будут выдавать только 3 слова?

5. Да, вы можете расширить его из любого диапазона, но если учесть тот факт, что вы можете использовать только 6 букв, фразы должны начинаться с g, h или i, вы можете значительно уменьшить размер проблемы.