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

Question

Если у меня есть список строк, например:

["car", "tree", "boy", "girl", "arc"...]

Что я должен сделать, чтобы найти анаграммы в этом списке?Например (car, arc).Я попытался использовать цикл for для каждой строки, и я использовал if, чтобы игнорировать строки различной длины, но я не могу получить правильный результат.

Как я могу просмотреть каждую букву в строке и сравнить ее с другими в списке в другом порядке?

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

Answer 1

Чтобы сделать это для 2 строк, вы можете сделать это:

def isAnagram(str1, str2):
    str1_list = list(str1)
    str1_list.sort()
    str2_list = list(str2)
    str2_list.sort()

    return (str1_list == str2_list)

Что касается итерации в списке, она довольно проста

Answer 2

Создать словарь (отсортированное слово, список слов).Все слова в одном списке являются анаграммами друг друга.

from collections import defaultdict

def load_words(filename='/usr/share/dict/american-english'):
    with open(filename) as f:
        for word in f:
            yield word.rstrip()

def get_anagrams(source):
    d = defaultdict(list)
    for word in source:
        key = "".join(sorted(word))
        d[key].append(word)
    return d

def print_anagrams(word_source):
    d = get_anagrams(word_source)
    for key, anagrams in d.iteritems():
        if len(anagrams) > 1:
            print(key, anagrams)

word_source = load_words()
print_anagrams(word_source)

Или:

word_source = ["car", "tree", "boy", "girl", "arc"]
print_anagrams(word_source)

Answer 3

Одним из решений является сортировка слова, которое вы ищете в анаграммах (например, с использованием sorted), сортировка альтернативы и сравнение их.

Так что, если вы будете искать анаграммы 'rac' в списке ['car', 'girl', 'tofu', 'rca'], ваш код может выглядеть следующим образом:

word = sorted('rac')
alternatives = ['car', 'girl', 'tofu', 'rca']

for alt in alternatives:
    if word == sorted(alt):
        print alt

Answer 4

Сортировка каждого элемента, а затем поиск дубликатов. Есть встроенная функция сортировки, поэтому вам не нужно ничего импортировать

Answer 5

Существует несколько решений этой проблемы:

1. Классический подход

   Сначала давайте рассмотрим, что определяет анаграмму: два слова являются анаграммами друг друга, если они состоят из одного и того же набора букв, и каждая буква появляется в обоих словах с одинаковой цифрой или временем .Это в основном гистограмма количества букв каждого слова.Это идеальный вариант использования для collections.Counter структуры данных ( см. Документы ).Алгоритмы следующие:

   • Создайте словарь, в котором ключами будут гистограммы, а значениями будут списки слов, которые имеют эту гистограмму.
   • Для каждого построения слова это гистограмма и добавьте еев список, который соответствует этой гистограмме.
   • Вывод списка значений словаря.

   Вот код:

   from collections import Counter, defaultdict
   
   def anagram(words):
       anagrams = defaultdict(list)
       for word in words:
           histogram = tuple(Counter(word).items()) # build a hashable histogram
           anagrams[histogram].append(word)
       return list(anagrams.values())
   
   keywords = ("hi", "hello", "bye", "helol", "abc", "cab", 
                   "bac", "silenced", "licensed", "declines")
   
   print(anagram(keywords))
   

   Обратите внимание, что построение Counterравен O(l), а сортировка каждого слова - O(n*log(l)), где l - длина слова.

2. Решение анаграмм с использованием простых чисел

   Это более продвинутое решение, основанное на «мультипликативной уникальности» простых чисел.Вы можете обратиться к этой публикации SO: Сравнение анаграмм с использованием простых чисел , и - это пример реализации Python .

Answer 6

Так как вы ничего не можете импортировать, вот два разных подхода, включая запрашиваемый цикл for.

Подход 1: для циклов и встроенной сортированной функции

word_list = ["percussion", "supersonic", "car", "tree", "boy", "girl", "arc"]

# initialize a list
anagram_list = []
for word_1 in word_list: 
    for word_2 in word_list: 
        if word_1 != word_2 and (sorted(word_1)==sorted(word_2)):
            anagram_list.append(word_1)
print(anagram_list)

Подход 2: Словари

def freq(word):
    freq_dict = {}
    for char in word:
        freq_dict[char] = freq_dict.get(char, 0) + 1
    return freq_dict

# initialize a list
anagram_list = []
for word_1 in word_list: 
    for word_2 in word_list: 
        if word_1 != word_2 and (freq(word_1) == freq(word_2)):
            anagram_list.append(word_1)
print(anagram_list)

ЕслиВы хотите, чтобы эти подходы были объяснены более подробно, вот статья .

Answer 7

Большинство предыдущих ответов верны, вот еще один способ сравнить две строки. Основным преимуществом использования этой стратегии по сравнению с сортировкой является сложность пространства / времени, которая составляет n log из n .

1.Проверьте длину строки

2.Введите словарь частот и сравните, если они совпадают, мы успешно определили слова анаграммы

def char_frequency(word):
    frequency  = {}
    for char in word:
        #if character  is in frequency then increment the value
        if char in frequency:
            frequency[char] += 1
        #else add character and set it to 1
        else:
            frequency[char] = 1
    return frequency 


a_word ='google'
b_word ='ooggle'
#check length of the words 
if (len(a_word) != len(b_word)):
   print ("not anagram")
else:
    #here we check the frequecy to see if we get the same
    if ( char_frequency(a_word) == char_frequency(b_word)):
        print("found anagram")
    else:
        print("no anagram")

Answer 8

def findanagranfromlistofwords(li):
    dict = {}
    index=0
    for i in range(0,len(li)):
        originalfirst = li[index]
        sortedfirst = ''.join(sorted(str(li[index])))
        for j in range(index+1,len(li)):
            next = ''.join(sorted(str(li[j])))
            print next
            if sortedfirst == next:
                dict.update({originalfirst:li[j]})
                print "dict = ",dict
        index+=1

    print dict

findanagranfromlistofwords(["car", "tree", "boy", "girl", "arc"])

Answer 9

вот впечатляющее решение.

func alphabet_count_mapper:

для каждого слова в файле / списке

1.создать словарь алфавитов / символов с начальным счетомкак 0.

2. сохранить счетчик всех алфавитов в слове и увеличить счетчик в указанном выше алфавите.

3.создать счетчик алфавита и вернуть кортеж из значенийАлфавит dict.

func anagram_counter:

1.создать словарь с кортежем алфавита в качестве ключа и счетчиком количества совпадений против него.

2.iterate overприведенный выше дикт и если значение> 1, добавьте значение к счетчику анаграмм.

    import sys
    words_count_map_dict = {}
    fobj = open(sys.argv[1],"r")
    words = fobj.read().split('\n')[:-1]

    def alphabet_count_mapper(word):
        alpha_count_dict = dict(zip('abcdefghijklmnopqrstuvwxyz',[0]*26))
        for alpha in word:
            if alpha in alpha_count_dict.keys():
                alpha_count_dict[alpha] += 1
            else:
                alpha_count_dict.update(dict(alpha=0))
        return tuple(alpha_count_dict.values())

    def anagram_counter(words):
        anagram_count = 0
        for word in words:
            temp_mapper = alphabet_count_mapper(word)
            if temp_mapper in words_count_map_dict.keys():
                words_count_map_dict[temp_mapper] += 1
            else:
                words_count_map_dict.update({temp_mapper:1})
        for val in words_count_map_dict.values():
            if val > 1:
                anagram_count += val
        return anagram_count


    print anagram_counter(words)

запустите его с путем к файлу в качестве аргумента командной строки

Answer 10

Это прекрасно работает:

def find_ana(l):
    a=[]
    for i in range(len(l)):
        for j in range(len(l)): 
            if (l[i]!=l[j]) and (sorted(l[i])==sorted(l[j])):
                a.append(l[i])
                a.append(l[j])

    return list(set(a))