Неэффективный решатель анаграмм

Question

Неэффективный решатель анаграмм

Следующая программа в основном генерирует анаграмму и приступает к ее решению:

#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<string>
#include<time.h>
using namespace std;
int random(){
int val = rand() % 26+1;
return val;
}
void main(){
srand(time(NULL));
int b = 0, j = 0, x = 0; int count = 0;
string line;
vector<string>str;
vector<string>chk;
vector < int > v(8);
vector <char> v1;
vector <char > ::iterator p;
vector <int > ::iterator p3;
vector <char > ::iterator p2;
while (b != 1){
for (int i = 0; i < 8; i++){
v[i] = random();
}
for (int i = 0; i < 8; i++){
v1.push_back('a' + (v[i]-1));
cout << v1[i];
}
string nam(v1.begin(), v1.end());
sort(nam.begin(), nam.end());
do {
str.push_back(nam);
count++;
} while (next_permutation(nam.begin(),nam.end()));
std::sort(v.begin(), v.end());
char d = 'a'+v[7];//Comparision is case sensitive, so the letter should be lowercase//
cout << endl;
ifstream myfile("List of all words.txt");
if (myfile.is_open())
{
while (getline(myfile, line))
{
if (line.find(d) == 0){
/*cout << line << "\n"; */
break;
}
else{
for (int i = 0; i < count; i++){
if (str[i].find(line) == 0){
cout << line << "\n";
break;
}
}
}
}
myfile.close();
}
cout << endl << count;

cin >> b;
}
}

Я включил файл, который содержит список слов на английском языке. Теперь моя проблема в том, что программа работает слишком медленно, тем более что каждое слово в словаре сравнивается примерно с 40320 словами, в зависимости от того, найдено или нет совпадение. Поэтому мне было интересно, есть ли у кого-нибудь какие-либо советы или предложения о том, как сделать этот код более эффективным и менее трудоемким.

-3

algorithm anagram c++

Решение

Другие решения

Источник

Accepted Answer

Вы можете избежать проверки каждой перестановки по словарю, создав словарь анаграммы. Это потребует гораздо больше места, но ускорит поиск решений.

Более простой альтернативой является сохранение словаря с помощью ключа, составленного из отсортированных по алфавиту букв каждого слова. Вы можете так сократить список кандидатов до минимума.

Здесь пошаговый подход

Вместо того, чтобы проходить каждый раз последовательно ваш файл, я предлагаю вам загрузить файл в задавать.

// load accepted words
set<string>mydict;
ifstream myfile("List of all words.txt");
if(!myfile) {
cerr << "Dictionnary file couldn't be loaded !\n";
return 1;
}
istream_iterator<string> eof;
istream_iterator<string> iit(myfile);
copy(iit, eof, inserter(mydict, mydict.begin())); // copy file to set
cout << mydict.size() << " words loaded\n";

Набор загружается только один раз в память. Поскольку он использует эффективный алгоритм поиска в O (log n), вы уже испытаете резкое увеличение производительности.

while(b != 1)
{
count = 0;
v.clear();
for(int i = 0; i < 8; i++)   // construct random anagram
v.push_back('a' + (random() - 1));
string nam(v.begin(), v.end());
cout << "Anagram:" << nam << endl;
std::sort(nam.begin(), nam.end());  // for using next permut()
do {                 // check if any of the permutation is in the set
if(mydict.find(nam) != mydict.end()) {
cout << "Found:" << nam << endl;  // bingo !!!
count++;
}
} while(next_permutation(nam.begin(), nam.end()));
if(count == 0)
cout << "Not found!"<<endl;

cin >> b;
}

Следующим шагом является создание карта, который отображает строку (отсортированные по алфавиту буквы анаграммы) в список совпадающих слов. В основном алфавитный вид букв слова — это анаграмма всех анаграмм слова. Таким образом, все слова для одного и того же ключа соответствуют одним и тем же анаграммам.

// compute anagram map
map<string, set<string>>myanadict;
for(auto x : mydict) {  // for every word in the dictionaly
string alph=x;
sort(alph.begin(), alph.end());  // sort the letters
myanadict[alph].insert(x);
}

Ну, теперь это становится прямо вперед

while(b != 1)
{
count = 0;
v.clear();
for(int i = 0; i < 8; i++)
v.push_back('a' + (random() - 1));
string nam(v.begin(), v.end());
//string nam = "dixeif";  // that was to test fixed values in my very smal file ;-)
cout << "Anagram:" << nam << endl;
std::sort(nam.begin(), nam.end());  // sort now for the map search
if (myanadict.find(nam)!=myanadict.end()) { // check if there's an entry
cout << "Found:";    // bingo !!!
copy(myanadict[nam].begin(), myanadict[nam].end(), ostream_iterator<string>(cout, " "));  // show all
}
else cout << "Not found!"<<endl;

1