Using Python find anagrams for a list of words

Question

If I have a list of strings for example     car    tree    boy    girl    arc        What should I do in order to find anagrams in that list  For example  car  arc   I tried using for loop for each string and I used if in order to ignore strings in different lengths but I can t get the right result    How can I go over each letter in the string and compare it to others in the list in different order   I have read several similar questions  but the answers were too advanced  I can t import anything and I can only use basic functions

User · Answer

This one is gonna help you   Assuming input is given as comma separated strings  console input  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

User · Answer

gt  gt  gt  words     car    race    rac    ecar    me    em    gt  gt  gt  anagrams          for word in words          reverse word word   -1          if reverse word in words              anagrams word     words pop words index reverse word     gt  gt  gt  anagrams 20    car    rac    me    em    race    ecar     Logic    Start from first word and reverse the word  Check the reversed word is present in the list  If present  find the index and pop the item and store it in the dictionary  word as key and reversed word as value

User · Answer

There are multiple solutions to this problem    Classic approach  First  let s consider what defines an anagram  two words are anagrams of each other if they consist of the same set of letters and each letter appears exactly the same number or time in both words  This is basically a histogram of letters count of each word  This is a perfect use case for collections Counter data structure  see docs   The algorithms is as follows    Build a dictionary where keys would be histograms and values would be lists of words that have this histogram  For each word build it s histogram and add it to the list that corresponds to this histogram  Output list of dictionary values    Here is the code   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     Note that constructing Counter is O l   while sorting each word is O n log l   where l is the length of the word  Solving anagrams using prime numbers  This is a more advanced solution  that relies on the  multiplicative uniqueness  of prime numbers  You can refer to this SO post  Comparing anagrams using prime numbers  and here is a sample python implementation

User · Answer

def all anagrams words   str   - gt   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

User · Answer

Simply use the Counter method available in Python3 collections package   str1  abc  str2  cab   Counter str1   Counter str2    returns True i e both Strings are anagrams of each other

User · Answer

A set is an appropriate data structure for the output  since you presumably don t want redundancy in the output  A dictionary is ideal for looking up if a particular sequence of letters has been previously observed  and what word it originally came from  Taking advantage of the fact that we can add the same item to a set multiple times without expanding the set lets us get away with one for loop   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   A faster way of doing it takes advantage of the commutative property of addition   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

User · Answer

In order to do this for 2 strings you can do this     def isAnagram str1  str2       str1 list   list str1      str1 list sort       str2 list   list str2      str2 list sort        return  str1 list    str2 list    As for the iteration on the list  it is pretty straight forward

User · Answer

Since you can t import anything  here are two different approaches including the for loop you asked for    Approach 1  For Loops and Inbuilt Sorted Function  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    Approach 2  Dictionaries  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    If you want these approaches explained in more detail  here is an article

User · Answer

Most of previous answers are correct  here is another way to compare two strings  The main benefit of using this strategy versus sort is space time complexity which is n log of n    1 Check the length of string  2 Build frequency Dictionary and compare if they both match then we have successfully identified anagram words  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

User · Answer

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

User · Answer

You convert each of the character in a word into a number  by ord   function   add them up for the word  If two words have the same sum  then they are anagrams  Then filter for the sums that occur more than twice in the list   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   gt  1

User · Answer

If you want a solution in java    public List lt String gt  findAnagrams List lt String gt  dictionary            TODO do null check and other basic validations      Map lt String  List lt String gt  gt  wordMap   new HashMap lt String  List lt String gt  gt          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 lt  gt     word                          List lt String gt  anagrams   new ArrayList lt  gt          for String key   wordMap keySet               if wordMap get key  size    gt  1                anagrams addAll wordMap get key                          return anagrams

User · Answer

Simple Solution in 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

User · Answer

here is the impressive solution   funct alphabet count mapper   for each word in the file list  1 create a dictionary of alphabets characters with initial count as 0   2 keep count of all the alphabets in the word and increment the count in the above alphabet dict   3 create alphabet count dict and return the tuple of the values of alphabet dict   funct anagram counter   1 create a dictionary with alphabet count tuple as key and the count of the number of occurences against it   2 iterate over the above dict and if the value   1  add the value to the anagram count       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  gt  1                  anagram count    val         return anagram count       print anagram counter words    run it with file path as command line argument

User · Answer

Sort each element then look for duplicates  There s a built-in function for sorting so you do not need to import anything

User · Answer

This works fine     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

User · Answer

I m using a dictionary to store each character of string one by one  Then iterate through second string and find the character in the dictionary  if it s present decrease the count of the corresponding key from dictionary   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

User · Answer

One solution is to sort the word you re searching anagrams for  for example using sorted   sort the alternative and compare those   So if you would be searching for anagrams of  rac  in the list   car    girl    tofu    rca    your code could look like this   word   sorted  rac   alternatives     car    girl    tofu    rca    for alt in alternatives      if word    sorted alt           print alt

User · Answer

Solution in python can be as below   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      First create a duplicate list of same words with indexes representing their position indexes  Then sort the individual strings of the duplicate list  Then sort the duplicate list itself based on strings  Finally print the original list with indexes used from duplicate array    The time complexity of above is O NMLogN   NMLogM    O NMlogN

User · Answer

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  gt  1      return  i for i in x if    join sorted list i    in anagrams counts

User · Answer

Calculate each word length   Calculate each word ascii character sum  Sort each word characters by their ascii values and set ordered word  Group words according to their lengths  For each group regroup list according to their ascii character sum  For each small list check only words ordered  If ordered words same these words anagram    Here we have 1000 000 words list  1000 000 words       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 lt string gt  m Words               private ConcurrentBag lt string gt  m CacheWords               private ConcurrentBag lt WordDef gt  m Anagramlist              public AngramTestForm                                 InitializeComponent                    m CacheWords   new ConcurrentBag lt string gt                                private void button1 Click object sender  EventArgs e                                m Words   null                  m Anagramlist   null                   m Words   new ConcurrentBag lt string gt                     m Anagramlist   new ConcurrentBag lt WordDef gt                      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 lt WordDef gt  wordDef   new List lt WordDef gt                      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   gt  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 lt WordDef gt  wordDef   new ConcurrentBag lt WordDef gt                      Parallel ForEach m Words  w   gt                                                WordDef wd   new WordDef                            wd Word   w                          wd WordSum   wd GetAsciiSum w                           wd Length   w Length                          wd Ordered   String Concat w OrderBy c   gt  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 lt WordDef gt  wd   wList ToList lt WordDef gt                          var tempWordsBySum   from w in wd                                          group w by w WordSum into newGroup                                          orderby newGroup Key                                          select newGroup                       Parallel ForEach tempWordsBySum  ws   gt                                                        List lt WordDef gt  we   ws ToList lt WordDef gt                                  if  we Count  gt  1                                                                CheckCandidates we                                                                                                          private void CheckCandidates List lt WordDef gt  we                                for  int i   0  i  lt  we Count  i                                          for  int j   i   1  j  lt  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

User · Answer

Create a dictionary of  sorted word  list of word   All the words that are in the same list are anagrams of each other   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   gt  1              print key  anagrams   word source   load words   print anagrams word source    Or   word source     car    tree    boy    girl    arc   print anagrams word source

User · Answer

list of words words     quot ROOPA quot   quot TABU quot   quot OOPAR quot   quot BUTA quot   quot BUAT quot     quot PAROO quot   quot Soudipta quot            quot Kheyali Park quot    quot Tollygaunge quot    quot AROOP quot   quot Love quot   quot AOORP quot             quot Protijayi quot   quot Paikpara quot   quot dipSouta quot   quot Shyambazaar quot            quot jayiProti quot    quot North Calcutta quot    quot Sovabazaar quot     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           The Output     ROOPA    OOPAR    PAROO    AROOP    AOORP     TABU    BUTA    BUAT     Soudipta    dipSouta     Kheyali Park     Tollygaunge     Love     Protijayi    jayiProti     Paikpara     Shyambazaar     North Calcutta     Sovabazaar

[python] Using Python, find anagrams for a list of words

Examples related to python

Examples related to anagram