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

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

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

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

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)

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

Большинство предыдущих ответов верны, вот еще один способ сравнить две строки. Основным преимуществом использования этой стратегии по сравнению с сортировкой является пространственно-временная сложность, которая составляет n log of 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")

Решение в 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()

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

Временная сложность выше составляет O (NMLogN + NMLogM) = O (NMlogN)

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

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

Простое решение на 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)

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

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

консольный ввод: 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

Это отлично работает:

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

# list of words
words = ["ROOPA","TABU","OOPAR","BUTA","BUAT" , "PAROO","Soudipta",
        "Kheyali Park", "Tollygaunge", "AROOP","Love","AOORP",
         "Protijayi","Paikpara","dipSouta","Shyambazaar",
        "jayiProti", "North Calcutta", "Sovabazaar"]

#Method 1
A = [''.join(sorted(word)) for word in words]

dict ={}

for indexofsamewords,samewords in enumerate(A):
    dict.setdefault(samewords, []).append(indexofsamewords)
    
print(dict)
#{'AOOPR': [0, 2, 5, 9, 11], 'ABTU': [1, 3, 4], 'Sadioptu': [6, 14], ' KPaaehiklry': [7], 'Taeggllnouy': [8], 'Leov': [10], 'Paiijorty': [12, 16], 'Paaaikpr': [13], 'Saaaabhmryz': [15], ' CNaachlortttu': [17], 'Saaaaborvz': [18]}

for index in dict.values(): 
    print( [words[i] for i in index ] )
    

Выход :

['ROOPA', 'OOPAR', 'PAROO', 'AROOP', 'AOORP']
['TABU', 'BUTA', 'BUAT']
['Soudipta', 'dipSouta']
['Kheyali Park']
['Tollygaunge']
['Love']
['Protijayi', 'jayiProti']
['Paikpara']
['Shyambazaar']
['North Calcutta']
['Sovabazaar']

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

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

Просто используйте метод счетчика, доступный в пакете коллекций Python3.

str1="abc"
str2="cab"

Counter(str1)==Counter(str2)
# returns True i.e both Strings are anagrams of each other.

1. Вычислите длину каждого слова.
2. Вычислить сумму символов ascii каждого слова.
3. Отсортируйте символы каждого слова по их значениям ascii и установите упорядоченное слово.
4. Сгруппируйте слова по их длине.
5. Для каждой группы перегруппируйте список в соответствии с их суммой символов ascii.
6. Для каждого небольшого списка проверяйте только упорядоченные слова. Если упорядоченные слова же эти слова анаграммы.

Здесь у нас есть список из 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;
            }
        }
    }

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

функцияalpha_count_mapper:

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

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

2. Продолжайте считать все алфавиты в слове и увеличивайте количество в приведенном выше алфавитном словаре.

3.создайте диктофон подсчета алфавита и верните кортеж значений диктофона алфавита.

функция anagram_counter:

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

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)

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

Вы конвертируете каждый символ в слове в число (с помощью функции 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]

>>> 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'}

Логика:

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

Если вы хотите решение в 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;
}