Если у меня есть список строк, например:
["car", "tree", "boy", "girl", "arc"...]
Что мне делать, чтобы найти анаграммы в этом списке? Например (car, arc).
Я попытался использовать для цикла для каждой строки, и я использовал if, чтобы игнорировать строки разной длины, но я не могу получить правильный результат.
Как я могу перебирать каждую букву в строке и сравнивать ее с другими в списке в другом порядке?
Я прочитал несколько подобных вопросов, но ответы были слишком продвинутыми. Я ничего не могу импортировать, и я могу использовать только основные функции.
Чтобы сделать это для 2 строк, вы можете сделать это:
def isAnagram(str1, str2):
str1_list = list(str1)
str1_list.sort()
str2_list = list(str2)
str2_list.sort()
return (str1_list == str2_list)
Что касается итерации в списке, это довольно прямолинейно
Создайте словарь (отсортированное слово, список слов). Все слова, входящие в один список, являются анаграммами друг друга.
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)
Одним из решений является сортировка слова, которое вы ищете для анаграмм (например, с помощью sorted), сортировки альтернативы и сравнения их.
Итак, если вы будете искать анаграммы "rac" в списке ['car', 'girl', 'tofu', 'rca'], ваш код может выглядеть так:
word = sorted('rac')
alternatives = ['car', 'girl', 'tofu', 'rca']
for alt in alternatives:
if word == sorted(alt):
print alt
Отсортируйте каждый элемент, затем найдите дубликаты. Там есть встроенная функция для сортировки, поэтому вам не нужно ничего импортировать
Существует несколько решений этой проблемы:
Классический подход
Во-первых, рассмотрим, что определяет анаграмму: два слова являются анаграммами друг друга, если они состоят из одного и того же набора букв, и каждая буква имеет одинаковое число или время в обоих словах. Это в основном гистограмма числа букв каждого слова. Это идеальный вариант для структуры данных 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 реализация.
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"])
Большинство предыдущих ответов верны, вот еще один способ сравнить две строки. Основным преимуществом использования этой стратегии по сравнению с сортировкой является сложность пространства/времени, которая равна 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")
Поскольку вы ничего не можете импортировать, вот два разных подхода, включая запрашиваемый цикл 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)
Если вы хотите, чтобы эти подходы были объяснены более подробно, вот статья.
Решение в 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)
Я использую словарь для хранения каждого символа строки один за другим. Затем перебираем вторую строку и находим символ в словаре, если она присутствует, уменьшает количество соответствующего ключа из словаря.
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
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]
Простое решение в 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))
Набор является подходящей структурой данных для вывода, поскольку вы, по-видимому, не хотите избыточности в выходе. Словарь идеально подходит для поиска, если ранее наблюдалась определенная последовательность букв, и из какого слова оно изначально исходило. Воспользовавшись тем, что мы можем добавить один и тот же элемент к множеству несколько раз, не расширяя набор, мы можем уйти с одним из циклов.
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
Здесь у нас 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;
}
}
}
вот впечатляющее решение.
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)
запустить его с пути к файлу в качестве аргумента командной строки
Вы конвертируете каждый символ в слово в число (с помощью функции 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'}
Logic:
Если вам нужно решение в 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;
}