Thread: Anagram program

  1. #1
    Registered User cdonlan's Avatar
    Join Date
    Sep 2004
    Posts
    49

    Anagram program

    I cannot get this anagram program to work. Does anyone have any ideas. It finds the words in the dictionary,but i doesnt find any anagrams. Does any see a bug. Ive looked at this thing for like 6 hours.

    Code:
    // Program to find all anagrams of a given word, using a dictionary
    // read from a file
    #include <iostream>
    #include <fstream>
    #include <string>
    #include <vector>
    #include <algorithm>
    #include <iterator>
    using namespace std;
    
    int main() 
    {
      cout << "Anagram finding program:\n"
        << "finds all words in a dictionary that can\n"
        << "be formed with the letters of a given word.\n" << endl;
      cout << "First, enter the name of the file containing\n"
           << "the dictionary: " << flush;
      string dictionary_name; 
      cin >> dictionary_name;
      ifstream ifs(dictionary_name.c_str());
      if (!ifs.is_open()) {
        cout << "Eh? Could not open file named "
             << dictionary_name << endl;
        exit(1);
      }
      cout << "\nReading the dictionary ..." << flush;
      typedef istream_iterator<string> string_input;
      vector<string> dictionary;
      copy(string_input(ifs), string_input(), 
           back_inserter(dictionary));
      cout << "\nThe dictionary contains " 
        << dictionary.size() << " words.\n\n";
      cout << "Now type a word (or any string of letters),\n"
        << "and I'll see if it has any anagrams: " << flush;
      for (string_input j(cin); j != string_input(); ++j) {
        string word = *j;
        sort(word.begin(), word.end());
        bool found_one = false;
        do {
          if (binary_search(dictionary.begin(),
                            dictionary.end(), 
                            word)) {
            cout << "  " << word << endl;
            found_one = true;
          }
        } while (next_permutation(word.begin(), word.end()));
        if (!found_one) 
          cout << "  Sorry, none found.\n";
        cout << "\nType another word " 
             << "(or the end-of-file char to stop): " << flush;
      }
      return 0;
    }
    thanks

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    Is your dictionary file sorted? You aren't sorting the contents after reading it into the vector and the binary_search function needs to operate on a sorted container.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  3. #3
    Registered User cdonlan's Avatar
    Join Date
    Sep 2004
    Posts
    49
    Ok thanks, would it be better to sort the text file or call a function to do it?

  4. #4
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146
    Well, I'd think a dictionary file should be sorted to begin with, so just make sure that the file you're using is.

    As for which is better, that's up to you. You could pass the vector containing the dictionary off to a function isSorted() and throw an error if it's not (linear time). Or you could sort through the dictionary every time you run your program( n log n or even quadratic time). Or you could use a heap to store your dictionary so that it stays nicely sorted without your having to do much (n log n). Or you could just assume that your user will always give the program a sorted dictionary file (constant time).

  5. #5

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 02-21-2008, 10:39 AM
  2. Using variables in system()
    By Afro in forum C Programming
    Replies: 8
    Last Post: 07-03-2007, 12:27 PM
  3. BOOKKEEPING PROGRAM, need help!
    By yabud in forum C Programming
    Replies: 3
    Last Post: 11-16-2006, 11:17 PM
  4. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  5. My program, anyhelp
    By @licomb in forum C Programming
    Replies: 14
    Last Post: 08-14-2001, 10:04 PM