anagrams 재귀

Question

재귀를 사용하려고 시도하고 오버플로 오류가 발생합니다. 나는 무엇을해야할지 모르겠다.

내 기능 중 하나에 모든 애너그램을 제공하고 싶지만 어떻게해야할지 모르겠다. 나는 모든 것을 하나의 함수로 채울 수 없으므로 두 가지를 만들었습니다 : 하나는 anagram을 만드는 것이고 다른 하나는 사전을 검색하여 모든 일치를 찾는 것입니다. 하지만 효과가 없으며 무엇을해야할지 모르겠습니다. 그리고 내 아나그램 함수에서 순열 함수로 돌아가고 싶지만 문자열을 반환하지 않으면 할 수 없습니다. 나는 아무것도 돌려 보내지 않고 그 기능으로 되돌아 가야합니다.

#include <iostream> 
#include <fstream> 
#include <istream> 
#include <string> 
using namespace std; 

const int MAXRESULTS = 20; // Max matches that can be found 
const int MAXDICTWORDS = 30000; // Max words that can be read in 
const int MAXPERMUTATIONS = 720; //enough permutations for a 6 letter word 

           //Beginning of assignment functions 
//Read Dictionary function that uses recursion 
int readDictionary(istream &, string[]); 
//Permuation function 
int recursivePermute(string, const string[], int, string[]); 
//Print function 
void recurPrint(const string[], int); 
//swap characters in a string 
void swap(string*, string*); 
//permutation function 
string Permutator(string, int, int, int); 
// 

//End of Assignment functions 

int main() 
{ 
    string Permutations[MAXPERMUTATIONS]; 
    string results[MAXRESULTS]; 
    string dict[MAXDICTWORDS]; 
    ifstream dictfile;   // file containing the list of words 
    int nwords;    // number of words read from dictionary 
    string word; 

    dictfile.open("words.txt"); 
    if (!dictfile) { 
     cout << "File not found!" << endl; 
     return (1); 
    } 

    nwords = readDictionary(dictfile, dict); 

    cout << "Please enter a string for an anagram: "; 
    cin >> word; 
    //Make all the permutations and store them in an array 

    int numMatches = recursivePermute(word, dict, nwords, results); 
    if (numMatches == 0) 
     cout << "No matches found" << endl; 
    else 
     recurPrint(results, numMatches); 
} 
/*************************************************************************************************** 
Name: readDictionary 
input: ifstream reference, string array 
Description: This function returns the number of words added into the array from the dictionary. 
****************************************************************************************************/ 
int readDictionary(istream &file, string DicArr[]) 
{ 
    int counter = 0; 
    if (counter > MAXDICTWORDS) 
     return counter; 
    if (getline(file, DicArr[0])) 
    { 
     counter++; 
     return counter += readDictionary(file, DicArr + 1); 
    } 
    else 
     return counter; 
} 
/***************************************************************************************************** 
Name: recursivePermute 
Input: string, const string array, int, string array 
Description: Places all the permutations of word, which are found in dict into results. 
Returns the number of matched words found. This number should not be larger than 
MAXRESULTS since that is the size of the array. The size is the number of words 
inside the dict array. 
*******************************************************************************************************/ 
int recursivePermute(string word, const string dict[], int size, string results[]) 
{ 
    //count to iterate through the dictionary array and keep in bounds 
    //numresults to keep track of the number of results 
    int numResults = 0; 
    //if statement to if the number of results goes over the limit 
    if (numResults > MAXRESULTS) 
     return numResults; 
    if (size == 0) 
     return numResults; 
    //if there is a match check the dictionary 
    if (word == dict[0]) 
    { 
     results[0] = word; 
     numResults++; 
    } 
    numResults += recursivePermute(Permutator(word, 0, word.length() - 1, 0), dict + 1, size - 1, results); 

    return numResults; 
} 
/******************************************************************************************************* 
Name: recurPrint 
Input:const string array, int 
Description: Prints out the results 
*********************************************************************************************************/ 
void recurPrint(const string results[], int size) 
{ 
    if (size == 1) 
    { 
     cout << "matching word \"" << results[0] << "\" found!\n" << endl; 
     return; 
    } 
    if (size == 0) 
     return; 
    cout << results[size - 1]; 
    recurPrint(results, size - 1); 
} 
/**************************************************************************************************** 
name: swap 
input: string pointer 
description: This functions swaps two characters in a string 
*****************************************************************************************************/ 
void swap(string* a, string* b) 
{ 
    string temp; 
    temp = *a; 
    *a = *b; 
    *b = temp; 
} 
/****************************************************************************************************** 
********************************************************************************************************/ 
string Permutator(string word, int beg, int end, int count) 
{ 
    string a; 
    if (count == end) 
     return word; 
    if (beg == end) 
     return; 

    if(count <= end) 
     { 
      swap(word[beg], word[count]); 
      Permutator(word, beg + 1, end, count); 
      swap(word[beg], word[count]); 
      Permutator(word, beg, end, count + 1); 
     } 
} 
/****************************************************************************************************** 
*******************************************************************************************************/ 

좋아, 그래서 내 문제를 좁혔습니다. 이 함수는 문자열의 배열 인 사전에 대한 각 순열을 검사하는 다른 함수에 각 순열을 공급하는 데 사용하고 있습니다.

string Permutator(string word, int beg, int end, int count) 
{ 
    if (count == end) 
     return word; 
    if (beg == end) 


    if (count <= end) 
    { 
     swap(word[beg], word[count]); 
     Permutator(word, beg + 1, end, count); 
     swap(word[beg], word[count]); 

    } 

} 

가 무효 인 경우이 작동,하지만 나는 그것이 문자열을 반환해야하지만 내가 수익을 변경할 때 내 전체 알고리즘은 구타를 벗어나 입력합니다. 이 과제에서 재귀가 될 수있는 루프는 예상대로 작동하지 않습니다. 나는 내가 할 수있는 일이 무엇인지 모르는 아이디어가 있습니다.

Answer 1

std::map<std::string, std::vector<std::string>>는 적절한 것 같다

std::vector<std::string> allWords /*= */; 
std::map<std::string, std::vector<std::string>> dictionary; 

for (const std::string& word : allWords) { 
    auto w = word; 
    std::sort(w.begin(), w.end()); 
    dictionary[w].push_back(word); 
} 

그리고

std::vector<std::string> 
find_words_from_anagram(const std::map<std::string, std::vector<std::string>>& dictionary, 
         const std::string& word) 
{ 
    auto w = word; 
    std::sort(w.begin(), w.end()); 

    auto it = dictionary.find(w); 
    if (it == dictionary.end()) { 
     return {}; // No match. 
    } 
    return it->second; 
} 

트릭 대신 모든 순열에 대한 검사의 항목을 정상화하는 것입니다.