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)
1つの解決策は、アナグラムを検索している単語を並べ替えて（たとえば、を使用してsorted）、代替語を並べ替えて比較することです。
したがって、リストで「rac」のアナグラムを検索する場合['car', 'girl', 'tofu', 'rca']、コードは次のようになります。
word = sorted('rac')
alternatives = ['car', 'girl', 'tofu', 'rca']
for alt in alternatives:
if word == sorted(alt):
print alt
この問題には複数の解決策があります。
古典的なアプローチ
まず、アナグラムを定義するものを考えてみましょう。2つの単語が同じ文字のセットで構成され、各文字が両方の単語でまったく同じ数または時間で表示される場合、2つの単語は互いにアナグラムです。これは基本的に、各単語の文字数のヒストグラムです。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実装があります。
各要素を並べ替えてから、重複を探します。ソート機能が組み込まれているので、何もインポートする必要はありません
何もインポートできないため、要求したforループを含む2つの異なるアプローチがあります。
アプローチ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)
これらのアプローチをより詳細に説明したい場合は、ここに記事があります。
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"])
以前の回答のほとんどは正しいです。2つの文字列を比較する別の方法があります。ソートに対してこの戦略を使用する主な利点は、nの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")
def all_anagrams(words: [str]) -> [str]:
word_dict = {}
for word in words:
sorted_word = "".join(sorted(word))
if sorted_word in word_dict:
word_dict[sorted_word].append(word)
else:
word_dict[sorted_word] = [word]
return list(word_dict.values())
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）です。
私は辞書を使って文字列の各文字を1つずつ保存しています。次に、2番目の文字列を繰り返し処理し、辞書で文字を見つけます。文字が存在する場合は、辞書から対応するキーの数を減らします。
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))
# 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']
おそらく出力に冗長性が必要ないため、セットは出力に適したデータ構造です。辞書は、特定の文字のシーケンスが以前に観察されたかどうか、およびそれが元々どの単語から来たかを調べるのに理想的です。セットを拡張せずに同じアイテムをセットに複数回追加できるという事実を利用して、1つの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コレクションパッケージで利用可能なCounterメソッドを使用するだけです。
str1="abc"
str2="cab"
Counter(str1)==Counter(str2)
# returns True i.e both Strings are anagrams of each other.
これが印象的な解決策です。
functalphabet_count_mapper：
ファイル/リスト内の単語ごとに
1.初期カウントが0のアルファベット/文字の辞書を作成します。
2.単語内のすべてのアルファベットのカウントを維持し、上記のアルファベット辞書のカウントをインクリメントします。
3.アルファベットカウントdictを作成し、アルファベットdictの値のタプルを返します。
funct 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（）関数によって）数値に変換し、それらを単語に加算します。2つの単語の合計が同じである場合、それらはアナグラムです。次に、リストで2回以上発生する合計をフィルタリングします。
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'}
論理：
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;
}