#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, вы можете значительно уменьшить размер проблемы.