-
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
-
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.
-
Ok thanks, would it be better to sort the text file or call a function to do it?
-
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).
-
