Question

C++ PROJECT

Objectives

• To solve problems using vectors

• To apply sorting

Introduction

Two words are anagrams of each other if one can be produced by a reordering of letters of the other. For example, “resistance” and “ancestries” are a pair of anagrams. Another anagram pair is “admirer” and “married”.

Each anagram forms an equivalence relation since it is:

• reflexive (each word is an anagram of itself)

• symmetric (if w1 is an anagram of w2 then w2 is an anagram of w1)

• transitive (f w1 is an anagram of w2 and w2 is an anagram of w3 then w1 is an anagram of w3)

Given a list of words you are to separate the words into equivalence classes and list the classes that have the greatest number of members in lexicographical order.

Input The input will consist of a single test case. The first line contains 2 integers 0 < m, n (separated by a single space) which indicates the number of words to consider and the number of classes to print out. The next m lines will be a single word composed of lowercase alphabetical characters. Input should be read in from a file, named words.txt.

Output

Output the n largest anagram equivalence classes. If there are less than n classes, then output them all. Sort the classes by decreasing size. You can break ties lexicographically by the lexicographically smallest element. For each class output, print its size and its member words. Sort the member words lexicographically and print equal words only once. 2 Output should be to standard output (the console.)

Example Sample Input File (words.txt)

16 5

undisplayed

trace

tea

singleton

eta

eat

displayed

crate

cater

carte

caret

beta

beat

bate

ate

abet

Sample Output (to standard output)

Class of size 5: caret carte cater crate trace .

Class of size 4: abet bate beat beta .

Class of size 4: ate eat eta tea .

Class of size 1: displayed .

Class of size 1: singleton .

Note: The term “class” as used above refers to classification or category of anagrams, not class as in C++

Answer 1

Screenshot

---------------------------------------------------------------------

Program

//Header files
#include <iostream>
#include<fstream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
//Function prototypes
int countRepeated(vector<int> cnt);
bool anagramChecker(string str1, string str2);
void eraseElement(vector<int>& values, int val);
int main()
{
   //Variables for file read and store
   int count, classClassification;
   vector<string>words;
   vector<int>wordsCnt;
   string word;
   //File path
   ifstream in("words.txt");
   //Error check in file open
   if (!in) {
       cout << "File not found!!!" << endl;
       exit(0);
   }
   //Read first line
   in >> count >> classClassification;
   //Read file data into a vector
   for (int i = 0; i < count; i++) {
       in >> word;
       words.push_back(word);
       wordsCnt.push_back(word.length());
   }
   //Close file
   in.close();
   //For number of class
   int j = 0;
   //Display unti number of class
   while (j < classClassification) {
       //Find largest length words
       vector<string>classification;
       int cnt = countRepeated(wordsCnt);
       for (int i = 0; i < count; i++) {
           if (words[i].size() == cnt) {
               classification.push_back(words[i]);
           }
       }
       //Check the base condition
       if (classification.size() == 2 && classification.size() <= classClassification) {
           if (anagramChecker(classification[0], classification[1])) {
               cout << "Class of size " << classification.size() << ": ";
               for (int i = 0; i < classification.size(); i++) {
                   cout << classification[i] << " ";
               }
               cout << endl;
           }
           else {
               cout << "Class of size " << classification.size()-1 << ": "<< classification[0]<<endl;
               j++;
               if (j < classClassification) {
                   cout << "Class of size " << classification.size()-1 << ": " << classification[1] << endl;
               }
           }
          
       }
       //Otherwise
       else {
           //Create matched anagrams
           vector<string>match;
           match.push_back(classification[0]);
           for (int i = 1; i < classification.size(); i++) {
               if (anagramChecker(classification[0], classification[i])) {
                   if (!std::count(match.begin(), match.end(), classification[i])) {
                       match.push_back(classification[i]);
                   }
               }
           }
           //If it's size within class size given then display
           if (match.size() <= classClassification) {
               sort(match.begin(), match.end());
               cout << "Class of size " << match.size() << ": ";
               for (int i = 0; i < match.size(); i++) {
                   cout << match[i] << " ";
               }
               cout << endl;
           }
           eraseElement(wordsCnt, cnt);
           match.clear();
       }
       classification.clear();
       j++;
   }
}
//Function to get repeated length values
int countRepeated(vector<int> cnt) {
   // Sort the array
   sort(cnt.begin(), cnt.end());
   int max = 1, result = cnt[0], cur = 1;
   //Get maximum frequencied values
   for (int i = 1; i < cnt.size(); i++) {
       if (cnt[i] == cnt[i - 1])
           cur++;
       else {
           if (cur > max) {
               max = cur;
               result = cnt[i - 1];
           }
           cur = 1;
       }
   }
   if (cur> max)
   {
       max= cur;
       result = cnt[cnt.size() - 1];
   }
   return result;
}
//Function to check anagram
bool anagramChecker(string str1, string str2) {
   if (str1.length() != str2.length())
       return false;
   sort(str1.begin(), str1.end());
   sort(str2.begin(), str2.end());
   for (int i = 0; i < str1.length(); i++)
       if (str1[i] != str2[i])
           return false;
   return true;
}
//Function to erase already counted values
void eraseElement(vector<int>& values, int val) {
   int i = 0;
   while (i < values.size()) {
       if (values[i] == val) {
           values.erase(values.begin() + i);
       }
       else {
           i++;
       }

   }
}

-------------------------------------------------------------------------------

Output

Class of size 5: caret carte cater crate trace
Class of size 4: ate eat eta tea
Class of size 4: abet bate beat beta
Class of size 1: singleton
Class of size 1: displayed

---------------------------------------------------------------------

Note:-

I assume you are expecting this matching