Anagrams C++

jaxrpc
jaxrpc used Ask the Experts™
on
Hi,
i would like to group words together...for example.
i have 3 words in my dictionary
cater
trace
acert

i would like to for all the words in my dictionary pair them maybe using map

e.g
acert - cater
acert - trace

cater - acert
cater - trace

trace - cater
trace - acert

kinda loss....i am expecting my dictionary to have 30k+ words. How can i do it efficiently also. Thanks just some pointers and directions.
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
Top Expert 2012
Commented:
Use 'next_permuataion()', i.e. like

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>

using namespace std ;

void main()
{
    const char VECTOR_SIZE = 5 ;

    // Define a template class vector of chars
    typedef vector<char> CharVector ;

    //Define an iterator for template class vector of chars
    typedef CharVector::iterator CharVectorIt ;

    //Define an ostream iterator for chars
    typedef ostream_iterator<char> CharOstreamIt;

    CharVector Pattern(VECTOR_SIZE) ;

    CharVectorIt start, end, it ;

    CharOstreamIt outIt(cout, " ") ;

    start = Pattern.begin() ;   // location of first
                                      // element of Pattern

    end = Pattern.end() ;       // one past the location last
                                       // element of Pattern

    //Initialize vector Pattern
    Pattern[0] = 't' ;
    Pattern[1] = 'r' ;
    Pattern[2] = 'a' ;
    Pattern[3] = 'c' ;
    Pattern[4] = 'e' ;
    //sort the contents of Pattern, required by next_permutation
    sort(start, end, less<char>()) ;

    // prchar content of Pattern
    cout << "Before calling next_permutation...\n" << "Pattern: " ;
    for(it = start; it != end; it++)
        cout << *it;
    cout << "\n\n" ;

    // Generate all possible permutations

    cout << "After calling next_permutation...." << endl ;
    while ( next_permutation(start, end, less<char>()) )
    {
        copy(start, end, outIt) ;
        cout << endl ;
    }
}
jkr
Top Expert 2012

Commented:

Author

Commented:
hi, thanks for direction....but after generating the possible permutation...i would loop through the my 30k words in the dictionary to see if the permutation is in the dictionary and then add it to my key, value map.
but if i would to loop through 30k for each permutation, it will be slow i think...are there any better ways of solving this?
CompTIA Security+

Learn the essential functions of CompTIA Security+, which establishes the core knowledge required of any cybersecurity role and leads professionals into intermediate-level cybersecurity jobs.

jkr
Top Expert 2012

Commented:
Just add it to the map. A map will not accept any duplicates anyway.
you could use a multimap with key = sorted word, value = word.
to lookup, sort the word and use as key. eg.

#include <iostream>
#include <map>
#include <string>
#include <fstream>
#include <algorithm>
using namespace std ;

int main()
{
  multimap<string,string> lookup ;
  ifstream file( "dictionary.txt" ) ;
  string str ;
  while( file >> str )
  {
    string key = str ;
    sort( key.begin(), key.end() ) ;
    lookup.insert( pair<string,string>(key,str) ) ;
  }

  {
    string what ;
    cout << "enter word: " ; cin >> what ;
    sort( what.begin(), what.end() ) ;
    typedef multimap<string,string>::iterator iterator ;
    pair<iterator,iterator> bounds = lookup.equal_range(what) ;
    for( iterator iter = bounds.first ; iter != bounds.second ; ++iter )
      cout << iter->second << '\n' ;
  }

}

Author

Commented:
hi eleven_squared,
would you mind explaning while(file >> str) str is = "" how does file know how many bytes to read from the file so that for that n bytes is = to 1 word? what if the dictionary is newline delimited?

thks
str is a std::string; when reading from the file the string resizes itself to accommodate all chars read till a white space is encountered.
the word in the dictionay could be delimited by any white space (space, tab, newline etc.)

Author

Commented:
hi, thanks for the tips... i am finding out why some of the things done that way.....
guess i really need to do practise more....i have been learning for 1 month + but i took so long to think of how to do something which you can do within minutes.....
I wouldn't use a multimap (it has really a ugly and uncomfortable interface). Better use a

   map<string, vector<string> >   permMap;

where the key is the sorted permutation key (unique) and the vector contains all occurences. Read the dictionary file like eleven_sqared had showed (the strings either should be separated by space or by newline), make the sorted key and add it to the map by

        permMap[key].push_back(str);

if the key doesn't exist a vector was created. If it exists you'll get a reference to the existing vector. To get the output required you need to iterate the map and iterate each vector inside of the loop as well.

Regards, Alex

jaxrpc, do not loose heart. it takes time before programming starts looking really easy. everyone would have been in your position when they started out; i certainly was!

Author

Commented:
itsmeandnobodyelse, i will try out your suggestion too...
eleven squared : looks like the STL is really useful
yes, stl is really useful. you would find a lot of ways to do things in a much easier way once you are familiar with it.

Author

Commented:
i was looking at cppreference.com i am trying to find some info on the pair template...but i found nothing...which area is it under?
 
  while( ifs >> str )  // will stop at end of file or error
  {
    string key = str ;
    sort( key.begin(), key.end() ) ;
    permMap[key].push_back(str);
  }
  ifs.close();
  ofstream ofs("perm.txt");
  map<string, vector<string> >::iterator it;
  for (it = permMap.begin(); it != permMap.end(); ++it)
  {
         vector<string>& v = it->second;
         vector<string>::iterator vit1;
         for (vit1 = v.begin(); vit1 != v.end(); ++vit1)
         while (vit1 != v.end())
         {
              vector<string>::iterator vit2;
               for (vit2 = v.begin(); vit2 != v.end(); ++vit2)
               {
                   if (vit1 == vit2)
                         continue;
                  ofs << *vit1 << " - " << *vit2 << endl;
               }
           }
     }
     // close file
    ...

jkr
Top Expert 2012

Commented:
Don't know that site, but you can find more information on http://www.sgi.com/tech/stl/pair.html and http://www.sgi.com/tech/stl/PairAssociativeContainer.html
>>>> to find some info on the pair template...but i found nothing..
class pair is defined in <utility>. Maybe there is a topic in cppreference. You should get it via map as well.
>>>>         while (vit1 != v.end())
That line must be removed. I replaced it by the for loop above.

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial