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

Ответ 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)

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

Ответ 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)

Ответ 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

Ответ 4

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

Ответ 5

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

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

  Во-первых, рассмотрим, что определяет анаграмму: два слова являются анаграммами друг друга, если они состоят из одного и того же набора букв, и каждая буква имеет одинаковое число или время в обоих словах. Это в основном гистограмма числа букв каждого слова. Это идеальный вариант для структуры данных 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 - длина слова.

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

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

Ответ 6

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"])

Ответ 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")

Ответ 8

Поскольку вы ничего не можете импортировать, вот два разных подхода, включая запрашиваемый цикл 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)

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

Ответ 9

Решение в python может быть следующим:

class Word:
    def __init__(self, data, index):
        self.data = data
        self.index = index

def printAnagrams(arr):
    dupArray = []
    size = len(arr)

    for i in range(size):
        dupArray.append(Word(arr[i], i))

    for i in range(size):
        dupArray[i].data = ''.join(sorted(dupArray[i].data))

    dupArray = sorted(dupArray, key=lambda x: x.data)

    for i in range(size):
        print arr[dupArray[i].index]

def main():
    arr = ["dog", "act", "cat", "god", "tac"]

    printAnagrams(arr)

if __name__== '__main__':
    main()

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

Сложность по времени выше: O (NMLogN + NMLogM) = O (NMlogN)

Ответ 10

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

class Anagram:

    dict = {}

    def __init__(self):
        Anagram.dict = {}

    def is_anagram(self,s1, s2):
        print '***** starting *****'

        print '***** convert input strings to lowercase'
        s1 = s1.lower()
        s2 = s2.lower()

        for i in s1:
           if i not in Anagram.dict:
              Anagram.dict[i] = 1
           else:
              Anagram.dict[i] += 1

        print Anagram.dict

        for i in s2:
           if i not in Anagram.dict:
              return false
           else:
              Anagram.dict[i] -= 1

        print Anagram.dict

       for i in Anagram.dict.keys():
          if Anagram.dict.get(i) == 0:
              del Anagram.dict[i]

       if len(Anagram.dict) == 0:
         print Anagram.dict
         return True
       else:
         return False

Ответ 11

import collections

def find_anagrams(x):
    anagrams = [''.join(sorted(list(i))) for i in x]
    anagrams_counts = [item for item, count in collections.Counter(anagrams).items() if count > 1]
    return [i for i in x if ''.join(sorted(list(i))) in anagrams_counts]

Ответ 12

Простое решение в Python:

def anagram(s1,s2):

    # Remove spaces and lowercase letters
    s1 = s1.replace(' ','').lower()
    s2 = s2.replace(' ','').lower()

    # Return sorted match.
    return sorted(s1) == sorted(s2)

Ответ 13

Этот поможет тебе:

Предполагая, что входные данные даны в виде разделенных запятыми строк

консольный ввод: abc, bac, car, rac, pqr, acb, acr, abc

in_list = list()
in_list = map(str, raw_input("Enter strings seperated by comma").split(','))
list_anagram = list()

for i in range(0, len(in_list) - 1):
    if sorted(in_list[i]) not in list_anagram:
        for j in range(i + 1, len(in_list)):
            isanagram = (sorted(in_list[i]) == sorted(in_list[j]))
            if isanagram:
                list_anagram.append(sorted(in_list[i]))
                print in_list[i], 'isanagram'
                break

Ответ 14

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

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))

Ответ 15

Набор является подходящей структурой данных для вывода, поскольку вы, по-видимому, не хотите избыточности в выходе. Словарь идеально подходит для поиска, если ранее наблюдалась определенная последовательность букв, и из какого слова оно изначально исходило. Воспользовавшись тем, что мы можем добавить один и тот же элемент к множеству несколько раз, не расширяя набор, мы можем уйти с одним из циклов.

def return_anagrams(word_list):
    d = {}
    out = set()
    for word in word_list:
        s = ''.join(sorted(word))
        try:
            out.add(d[s])
            out.add(word)
        except:
            d[s] = word
    return out

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

import numpy as np

def vector_anagram(l):
    d, out = dict(), set()
    for word in l:
        s = np.zeros(26, dtype=int)
        for c in word:
            s[ord(c)-97] += 1
        s = tuple(s)
        try:
            out.add(d[s])
            out.add(word)
        except:
            d[s] = word
    return out

Ответ 16

• Рассчитайте длину каждого слова.
• Рассчитайте сумму символа слова ascii каждого слова.
• Сортируйте каждый символ слова по их значениям ascii и задайте упорядоченное слово.
• Групповые слова в соответствии с их длиной.
• Для каждого списка групп групп в соответствии с их суммой символов ascii.
• Для каждого небольшого списка проверяются только упорядоченные слова. Если упорядоченные слова совпадают с этими анаграммами.

Здесь у нас 1000 000 слов. 1000.000 слов

    namespace WindowsFormsApplication2
    {
        public class WordDef
        {
            public string Word { get; set; }
            public int WordSum { get; set; }
            public int Length { get; set; }       
            public string AnagramWord { get; set; }
            public string Ordered { get; set; }
            public int GetAsciiSum(string word)
            {
                int sum = 0;
                foreach (char c in word)
                {
                    sum += (int)c;
                }
                return sum;
            }
        }
    }

    using System;
    using System.Collections.Concurrent;
    using System.Collections.Generic;
    using System.Diagnostics;
    using System.Linq;
    using System.Net;
    using System.Text;
    using System.Threading.Tasks;
    using System.Windows.Forms;

    namespace WindowsFormsApplication2
    {
        public partial class AngramTestForm : Form
        {
            private ConcurrentBag<string> m_Words;

            private ConcurrentBag<string> m_CacheWords;

            private ConcurrentBag<WordDef> m_Anagramlist;
            public AngramTestForm()
            {
                InitializeComponent();
                m_CacheWords = new ConcurrentBag<string>();
            }

            private void button1_Click(object sender, EventArgs e)
            {
                m_Words = null;
                m_Anagramlist = null;

                m_Words = new ConcurrentBag<string>();
                m_Anagramlist = new ConcurrentBag<WordDef>();

                if (m_CacheWords.Count == 0)
                {
                    foreach (var s in GetWords())
                    {
                        m_CacheWords.Add(s);
                    }
                }

                m_Words = m_CacheWords;

                Stopwatch sw = new Stopwatch();

                sw.Start();

                //DirectCalculation();

                AsciiCalculation();

                sw.Stop();

                Console.WriteLine("The End! {0}", sw.ElapsedMilliseconds);

                this.Invoke((MethodInvoker)delegate
                {
                    lbResult.Text = string.Concat(sw.ElapsedMilliseconds.ToString(), " Miliseconds");
                });

                StringBuilder sb = new StringBuilder();
                foreach (var w in m_Anagramlist)
                {
                    if (w != null)
                    {
                        sb.Append(string.Concat(w.Word, " - ", w.AnagramWord, Environment.NewLine));
                    }
                }

                txResult.Text = sb.ToString();
            }

            private void DirectCalculation()
            {
                List<WordDef> wordDef = new List<WordDef>();

                foreach (var w in m_Words)
                {
                    WordDef wd = new WordDef();
                    wd.Word = w;
                    wd.WordSum = wd.GetAsciiSum(w);
                    wd.Length = w.Length;
                    wd.Ordered = String.Concat(w.OrderBy(c => c));

                    wordDef.Add(wd);
                }

                foreach (var w in wordDef)
                {
                    foreach (var t in wordDef)
                    {
                        if (w.Word != t.Word)
                        {
                            if (w.Ordered == t.Ordered)
                            {
                                t.AnagramWord = w.Word;
                                m_Anagramlist.Add(new WordDef() { Word = w.Word, AnagramWord = t.Word });
                            }
                        }
                    }
                }
            }

            private void AsciiCalculation()
            {
                ConcurrentBag<WordDef> wordDef = new ConcurrentBag<WordDef>();

                Parallel.ForEach(m_Words, w =>
                    {
                        WordDef wd = new WordDef();
                        wd.Word = w;
                        wd.WordSum = wd.GetAsciiSum(w);
                        wd.Length = w.Length;
                        wd.Ordered = String.Concat(w.OrderBy(c => c));

                        wordDef.Add(wd);                    
                    });

                var tempWordByLength = from w in wordDef
                                       group w by w.Length into newGroup
                                       orderby newGroup.Key
                                       select newGroup;

                foreach (var wList in tempWordByLength)
                {
                    List<WordDef> wd = wList.ToList<WordDef>();

                    var tempWordsBySum = from w in wd
                                         group w by w.WordSum into newGroup
                                         orderby newGroup.Key
                                         select newGroup;

                    Parallel.ForEach(tempWordsBySum, ws =>
                        {
                            List<WordDef> we = ws.ToList<WordDef>();

                            if (we.Count > 1)
                            {
                                CheckCandidates(we);
                            }
                        });
                }
            }

            private void CheckCandidates(List<WordDef> we)
            {
                for (int i = 0; i < we.Count; i++)
                {
                    for (int j = i + 1; j < we.Count; j++)
                    {
                        if (we[i].Word != we[j].Word)
                        {
                            if (we[i].Ordered == we[j].Ordered)
                            {
                                we[j].AnagramWord = we[i].Word;
                                m_Anagramlist.Add(new WordDef() { Word = we[i].Word, AnagramWord = we[j].Word });
                            }
                        }
                    }
                }
            }

            private static string[] GetWords()
            {
                string htmlCode = string.Empty;

                using (WebClient client = new WebClient())
                {
                    htmlCode = client.DownloadString("https://raw.githubusercontent.com/danielmiessler/SecLists/master/Passwords/10_million_password_list_top_1000000.txt");
                }

                string[] words = htmlCode.Split(new string[] { "\n" }, StringSplitOptions.RemoveEmptyEntries);

                return words;
            }
        }
    }

Ответ 17

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

funct alphabet_count_mapper:

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

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

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

3.Создайте алфавит count dict и верните кортеж значений алфавита dict.

funct anagram_counter:

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

2.Вставьте вышеописанный dict и, если значение > 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)

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

Ответ 18

Вы конвертируете каждый символ в слово в число (с помощью функции ord()), добавьте их для слова. Если два слова имеют одинаковую сумму, то они являются анаграммами. Затем фильтруйте суммы, которые встречаются более чем в два раза в списке.

def sumLet(w):
    return sum([ord(c) for c in w])

def find_anagrams(l):
    num_l = map(sumLet,l)
    return [l[i] for i,num in enumerate(num_l) if num_l.count(num) > 1]

Ответ 19

>>> words = ["car", "race", "rac", "ecar", "me", "em"]
>>> anagrams = {}
... for word in words:
...     reverse_word=word[::-1]
...     if reverse_word in words:
...         anagrams[word] = (words.pop(words.index(reverse_word)))
>>> anagrams
20: {'car': 'rac', 'me': 'em', 'race': 'ecar'}

Logic:

• Начните с первого слова и отмените слово.
• Проверьте, что в списке есть слово, отменяемое назад.
• Если присутствует, найдите индекс и поместите элемент и сохраните его в словаре, слово в качестве ключа и измените слово как значение.

Ответ 20

Если вам нужно решение в java,

public List<String> findAnagrams(List<String> dictionary) {

    // TODO do null check and other basic validations.
    Map<String, List<String>> wordMap = new HashMap<String, List<String>>();

    for(String word : dictionary) {

        // ignore if word is null
        char[] tempWord = word.tocharArray();
        Arrays.sort(tempWord);
        String newWord = new String(tempWord);

        if(wordMap.containsKey(newWord)) {
            wordMap.put(newWord, wordMap.get(word).add(word));
        } else {
            wordMap.put(newWord, new ArrayList<>() {word});
        }

    }

    List<String> anagrams = new ArrayList<>();

    for(String key : wordMap.keySet()) {

        if(wordMap.get(key).size() > 1) {
            anagrams.addAll(wordMap.get(key));
        }

    }

    return anagrams;
}