anagram c++

im trying to make a anagram finder. where it request the user of a word and searches the vector words to find all the anagrams of that word. i think my logic behind the program might be wrong is it possible for someone to help me .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
  #include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>
#include <map>
#include <unordered_map>



using namespace std;

class Files {
private:
    vector<string>words;

public:
    void printAnagram(unordered_map<string, vector<string> >& store);
    void storeInMap(vector<string>& vec);
    void runner();
    void read();
    struct Compare {
        std::string str;
        Compare(const std::string& x) : str(x) {
            std::sort(str.begin(), str.end()); std::transform(str.begin(),
                str.end(), str.begin(), ::toupper);
        }

        bool operator ()(const std::string& t)
        {
            std::string s = t;
            std::transform(s.begin(), s.end(), s.begin(), ::toupper);
            std::sort(s.begin(), s.end());

            return s == str;
        }
    };

};


void Files::read()
{
    string word;
    string definition;
    string type;
    string blank;
    int i = 0;
    ifstream file("Text.txt");

    if (!file) {
        cout << "Unable to locate file" << endl;
        exit(1);
    }

    while (file.good())
    {
        cout << "File loaded successfully." << endl;
        cout << "Extracting files. Please Wait....";
        do//Gets all the data from the text file and saves it to the vectors
        {
            getline(file, word, '\n');
            words.push_back(word); //pushes to the back of the words vector
            i++;

        } while (!file.eof());
        break;
    }
    file.close();


}

void Files::runner()
{
    string anagram;
    cout << "Enter a word to find all the anagrams : ";
    cin >> anagram;
    
   string count = copy_if(words.begin(), words.end(), Compare(anagram));

    cout << count << endl;
}


int main()
{

    Files d;
    d.read();

    d.runner();




    return 0;
}
Last edited on
logic seems solid, sort both and compare.
what exactly is it not doing correctly?
does the file contain spaces or other extras that are breaking it?
1
2
3
4
5
6
7
8
9
10
11
12
13
while (file.good())
    {
        cout << "File loaded successfully." << endl;
        cout << "Extracting files. Please Wait....";
        do//Gets all the data from the text file and saves it to the vectors
        {
            getline(file, word, '\n');
            words.push_back(word); //pushes to the back of the words vector
            i++;

        } while (!file.eof());
        break;
    }


can be simplified to:

1
2
3
4
5
6
7
8
        cout << "File loaded successfully." << endl;
        cout << "Extracting files. Please Wait....";

        while (getline(file, word)) {
            words.push_back(word); //pushes to the back of the words vector
            i++;

        }


The outer while loop is not needed as after the inner do=loop has exited, the file state will be eof and therefore the next time around the while loop, file.good() will fail. So this loop is only executed once. For the inner do loop, getline() returns the stream so that can be checked as part of loop so need to check for eof after. In any case you have a superfluous break after the do loop.

read() also has some unused variable definitions.

For runner(), copy_if() doesn't specify a result iterator - it takes 4 parameters, not 3. copy_if() also returns an iterator to the element that follows the last element written - not a string. Does this compile?

compare() sorts and then makes UC, whilst () makes UC and then sorts ??

1
2
3
4
5
6
7
8
 bool operator ()(const std::string& t)
        {
            std::string s = t;
            std::transform(s.begin(), s.end(), s.begin(), ::toupper);
            std::sort(s.begin(), s.end());

            return s == str;
        }


You don't need the explicit assignment here. You can pass the parameter by value and have the copy implicit:

1
2
3
4
5
6
7
 bool operator ()(std::string s)
        {
            std::transform(s.begin(), s.end(), s.begin(), ::toupper);
            std::sort(s.begin(), s.end());

            return s == str;
        }

Last edited on
I take it back that maybe incorrect.
Last edited on
You can't use copy_if(). That requires an output iterator into a collection that already has enough space for the result. Here's a version of runner that works with the rest of your code:
1
2
3
4
5
6
7
8
9
10
11
12
13
void Files::runner()
{
    string anagram;
    cout << "Enter a word to find all the anagrams : ";
    cin >> anagram;
    vector<string> result;
    Compare cmp(anagram);
    for (auto &s : words) {
        if (cmp(s)) {
            cout << s << '\n';
        }
    }
}

Using a large dictionary I had lying around:
File loaded successfully.
Extracting files. Please Wait....Enter a word to find all the anagrams : silent
LISTEN
SILENT
ENLIST
INLETS
SLINTE
TINSEL
You can't use copy_if(). That requires an output iterator into a collection that already has enough space for the result.


You can use the std::back_inserter() for an output iterator which can be used into say a vector. See http://www.cplusplus.com/reference/iterator/back_inserter/ which has an example (using copy() but same principle).

Consider:

1
2
3
4
5
6
7
8
9
10
11
void Files::runner()
{
    string anagram;
    cout << "Enter a word to find all the anagrams : ";
    cin >> anagram;

    vector<string> result;
    
    copy_if(words.begin(), words.end(), back_inserter(result), Compare(anagram));
    copy(result.begin(), result.end(), ostream_iterator<string>(cout, "\n"));
}  

Last edited on
Seeplus,

Nice. Thanks for pointing that out.
Continuously transforming/sorting the words vector for every word to be checked is not very efficient. In performance terms, you just need to transform/sort the words once and use this as the index for a map (can use unordered as not required to traverse in sorted order), together with a list of indexes into the words vector of the words with the same letters. Consider:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <cctype>
#include <unordered_map>

using namespace std;

class Files {
private:
	vector<string>words;
	unordered_map<string, vector<size_t>> anags;

public:
	void runner();
	void read();
};

void Files::read()
{
	string word;
	ifstream file("Words.txt");

	if (!file) {
		cout << "Unable to locate file" << endl;
		exit(1);
	}

	cout << "File loaded successfully." << endl;
	cout << "Extracting files. Please Wait....\n\n";

	while (getline(file, word)) {
		words.push_back(word);
		std::transform(word.begin(), word.end(), word.begin(), ::toupper);
		std::sort(word.begin(), word.end());
		anags[word].push_back(words.size() - 1);
	}

	file.close();
}

void Files::runner()
{
	string anagram;
	cout << "Enter a word to find all the anagrams : ";
	cin >> anagram;

	std::transform(anagram.begin(), anagram.end(), anagram.begin(), ::toupper);
	std::sort(anagram.begin(), anagram.end());

	if (const auto res = anags.find(anagram); res != anags.end())
		for (const auto& a : res->second)
			cout << words[a] << '\n';	// or add to vector etc etc
	else
		cout << "Not found\n";
}

int main()
{
	Files d;

	d.read();
	d.runner();
}

Last edited on
Continuously transforming/sorting the words vector for every word to be checked is not very efficient
It's a classic time vs. space problem. Using one takes half the space in exchange for increased run time, but only if you're looking up multiple words.

If you transform the words once, then it's easier to just map the anagram key directly to the anagram words. Also, it's a good idea to have a method that converts a word to its corresponding key.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <cctype>
#include <unordered_map>

using namespace std;

class Files {
private:
	// Maps anagram keys to corresponding words
	unordered_map<string, vector<string>> anags;
	string toKey(string word);	// convert a word to its anagram key
public:
	void runner();
	void read();
};

string Files::toKey(string word)
{
    std::transform(word.begin(), word.end(), word.begin(), ::toupper);
    std::sort(word.begin(), word.end());
    return word;
}

void Files::read()
{
	string word;
	ifstream file("Words.txt");

	if (!file) {
		cout << "Unable to locate file" << endl;
		exit(1);
	}

	cout << "Extracting files. Please Wait....\n\n";

	while (getline(file, word)) {
	    anags[toKey(word)].push_back(word);
	}
	cout << "File loaded successfully." << endl;
	file.close();
}

void Files::runner()
{
	string anagram;
	cout << "Enter a word to find all the anagrams : ";
	cin >> anagram;

	string key = toKey(anagram);

	if (const auto res = anags.find(key); res != anags.end()) {
	    for (const auto& word : res->second) {
		cout << word << '\n';	// or add to vector etc etc
	    }
	} else {
		cout << "Not found\n";
	}
}

int main()
{
	Files d;

	d.read();
	d.runner();
}

Also, it's a good idea to have a method that converts a word to its corresponding key.


:)


If you transform the words once, then it's easier to just map the anagram key directly to the anagram words.


but at the expense of duplicate stored words with no performance benefit. That's why I used a vector of indexes into the words vector. :)
Last edited on
but at the expense of duplicate stored words
How so? You may have missed that I removed the words vector completely.
Er well, hmm ah...

OK. Mea Culpa! I didn't read the code properly as I should have done - as I was talking on the phone at the same time.

:) :) :)
No problem. I thought I might have missed something that caused duplication.
Topic archived. No new replies allowed.