Неэффективный решатель анаграмм
Следующая программа в основном генерирует анаграмму и приступает к ее решению:
#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 словами, в зависимости от того, найдено или нет совпадение. Поэтому мне было интересно, есть ли у кого-нибудь какие-либо советы или предложения о том, как сделать этот код более эффективным и менее трудоемким.
Решение
Вы можете избежать проверки каждой перестановки по словарю, создав словарь анаграммы. Это потребует гораздо больше места, но ускорит поиск решений.
Более простой альтернативой является сохранение словаря с помощью ключа, составленного из отсортированных по алфавиту букв каждого слова. Вы можете так сократить список кандидатов до минимума.
Здесь пошаговый подход
Вместо того, чтобы проходить каждый раз последовательно ваш файл, я предлагаю вам загрузить файл в задавать.
// 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;
Другие решения