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

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

15 голосов
/ 27 ноября 2011

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

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

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

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

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

Ответы [ 20 ]

0 голосов
/ 07 марта 2018

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

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

консольный ввод: азбука, BAC, автомобиль, Рац, PQR, ACB, ACR, а 

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
0 голосов
/ 05 марта 2018

Простое решение на 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)
0 голосов
/ 27 ноября 2011 
>>> 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. Если имеется, найдите индекс, вытолкните элемент и сохраните его в словаре, слово в качестве ключа и обратное слово в качестве значения.
0 голосов
/ 21 апреля 2017

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

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
0 голосов
/ 08 августа 2017 
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]
0 голосов
/ 07 августа 2014

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

Решение в 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) * ​​1014 *

0 голосов
/ 22 ноября 2015

Набор - это подходящая структура данных для вывода, так как вы, вероятно, не хотите избыточности в выводе.Словарь идеально подходит для поиска, если ранее была обнаружена определенная последовательность букв и из какого слова она изначально произошла.Воспользовавшись тем фактом, что мы можем добавлять один и тот же элемент в набор несколько раз, не расширяя набор, мы можем использовать один цикл 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
0 голосов
/ 18 ноября 2015
  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;
            }
        }
    }
0 голосов
/ 06 марта 2015

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