Python: поиск анаграмм

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

Например:

base_string = 'Oscar Wilde'
words = {1: 'sidecar', 2: 'owl', 3: 'low', 4: 'acid', 5: 'bread', 6: 'slower'}

Теперь я хочу посмотреть, сколько разных анаграмм я могу составить со словами из словаря. Желаемый результат: «сова с коляской», «низкая коляска», «медленнее кислоты».

Я преобразовал строку в список, который выглядит так:

letters = ['o', 's', 'c', 'a', 'r', 'w', 'i', 'l', 'd', 'e']

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

anagrams = []
counter = 0
for i in range(1, len(words)+1):
    anagram = ''
    for i in range(i+1, len(words)+1):
        if contain(letters, words[i]):  #if word is contained in the base string
            for i in words[i]:  #remove each letter of the word from the list of letters of the base string 
                letters.remove(i)
            anagram += words[i] + ' '
    if len(letters) >= 1:  #if all the letters are not used, it's not an anagram
        counter += 1
    if len(letters) == 0:  #if all the letters are used, it's an anagram
        anagrams.append(anagram)

print anagrams

def contain(list1, list2):
    counter1 = Counter(list1)
    counter2 = Counter(list2)
    for k in counter2:
        if counter2[k] != counter1.get(k):
            return False
    return True

findanagram()

Я получаю KeyError для анаграммы += words[i] + ' '

Надеюсь, я объяснил себя достаточно хорошо.


python python-2.7 anagram
person Community    schedule 12.12.2015    source источник

Ответы (2)


arrow_upward
0
arrow_downward

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

Идея состоит в том, чтобы связать каждую букву с простым числом, т. е. a = 2, b = 3, c = 5 и т. д. Единственный способ получить число 25 — это дважды использовать букву c в вашем слове. Перемножив все буквы в слове, вы получите его идентификационный номер. Естественно, любые анаграммы этого слова также приведут к одному и тому же идентификатору.

Итак, все, что вам нужно, это проверить, что произведение идентификаторов слов A и B равно идентификатору интересующего вас слова.

from itertools import combinations
from string import ascii_lowercase as alphabet

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
          47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]
letter_id = dict(zip(alphabet, primes))

def get_word_id(word):
    product = 1
    for letter in word:
        product *= letter_id[letter]
    return product

words = ['sidecar', 'owl', 'low', 'acid', 'bread', 'slower']
dictionary = {}
for w in words:
    dictionary[w] = get_word_id(w)

base_string = 'Oscar Wilde'

for comb in combinations(words, 2):
    comb_id = 1
    for word in comb:
        comb_id *= dictionary[word]
    if get_word_id(base_string.replace(' ', '').lower()) == comb_id:
        print comb

Как я уже отмечал в ответе Хеге, если вас интересует больше, чем пары, вы можете обобщить такие комбинации

for no_of_words in xrange(1, len(words)+1):
    for comb in combinations(words, no_of_words):
        ...
person Reti43    schedule 12.12.2015
comment
как лучше всего подсчитать все перепробованные комбинации? Я попытался поставить «счетчик += 1» для гребенки в комбинациях (слова, отсутствие_слов), и это не работает. - person ; 12.12.2015
comment
Вы инициализировали счетчик вне внешнего цикла? Как именно это не сработало? Была ли ошибка? Существует также простое уравнение, которое даст вам количество комбинаций. - person Reti43; 12.12.2015
comment
я инициализировал его как counter = 0 перед циклом, и он выводит 0, как будто ничего не произошло - person ; 12.12.2015
comment
Я не могу воспроизвести вашу проблему. Можете ли вы загрузить точный блок кода, который вы используете на pastebin.com для проверки? - person Reti43; 12.12.2015

arrow_upward
0
arrow_downward

Пример реализации

Самый простой, но далеко не самый эффективный способ сделать это. Он будет искать анаграммы из двух слов:

from itertools import combinations
from collections import Counter

name = 'Oscar Wilde'
words = ['sidecar', 'owl', 'low', 'acid', 'bread', 'slower']

letter_counter = Counter(name.replace(' ', '').lower())
for ws in combinations(words, 2):
    if Counter(''.join(ws)) == letter_counter:
        print(' '.join(ws))

# sidecar owl
# sidecar low
# acid slower

В основном он делает то же самое, что и вы, но более питоническим способом.

Есть некоторые проблемы с вашей реализацией:

  • Ваша функция содержания не работает должным образом. Это даст false для contain('a', 'aa'), так как он проверяет количество встречающихся букв на равенство.
  • Ваши два цикла for используют одну и ту же индексную переменную i.
  • Вы используете индексы на основе 1 (range(1, len(words) + 1)) для массивов, но массивы python основаны на 0 (range(0, len(words)))
person Tamas Hegedus    schedule 12.12.2015
comment
Неясно, хочет ли ОП только пары слов, но вы можете обобщить комбинации с for no_of_words in xrange(1, len(words)+1): for ws in combinations(words, no_of_words): ... - person Reti43; 12.12.2015
comment
Да, но я не хочу записывать такой неэффективный алгоритм. Я обновлю свой ответ, чтобы было ясно, что он найдет пары! - person Tamas Hegedus; 12.12.2015
comment
Есть ли у анонимного downvoter какие-то советы для меня или, по крайней мере, объяснение, почему ему не нравится мое решение? - person Tamas Hegedus; 12.12.2015
comment
Это решение очень чистое. +1 - person poindexter; 17.04.2020