Given the above if you can help create a recursion function with its base cases

Question

Given the above if you can help create a recursion function with its base cases of the function below. Also Please no use of do, while, or for keywords, or any stl algortithms. In c++

int recursivePermute(string word, const string dict[], int size, string results[]);

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.

Explanation / Answer

#include <iostream>
#include <fstream>
#include <istream>
#include <cstring>
#include <string>

#include <chrono>

using namespace std;

const int MAXRESULTS   = 20;    // Max matches that can be found
const int MAXDICTWORDS = 30000; // Max words that can be read in

int readDictionary(istream &dictfile, string dict[]);

int recursivePermute(string word, const string dict[], int size, string results[]);

void recurPrint(const string results[], int size);

void permu_loop(int i, int max, string prefix, string rest, const string dict[], const int& size, string results[], int& count);

void findPermutations(string prefix, string rest, const string dict[], const int& size, string results[], int& count);

int checkDict(string target, const string dict[], int size, string results[], string result_spec[], int& count);

bool isDuplicated(string target, string results[], int start, int max);

int main()
{
    chrono::steady_clock::time_point begin = chrono::steady_clock::now();
  
    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);
  
    /************************* testing ***************************/
//    cout << nwords << endl;
//  
//    int i = 0;
//    while(i < 619)
//    {
//        cout << dict[i] << endl;
//        i++;
//    }
  
  
    // string exampleDict[] = {"kool", "moe", "dee"};
    // int numResults = recursivePermute("look", exampleDict, 3, results);
    // assert(numResults == 1 && results[0] == "kool");
  
    /************************* testing ***************************/
  
    cout << "Please enter a string for an anagram: ";
    cin >> word;
  
    int numMatches = recursivePermute(word, dict, nwords, results);
    if (!numMatches)
        cout << "No matches found" << endl;
    else
        recurPrint(results, numMatches);
  
  
    dictfile.close();
  
    chrono::steady_clock::time_point end= chrono::steady_clock::now();
  
    cout << "Time difference (sec) = " << (chrono::duration_cast<chrono::microseconds>(end - begin).count()) /1000000.0 << endl;
  
  
  
}

// Places each string in dictfile into the array dict. Returns the number of words read into dict.
// This number should not be larger than MAXDICTWORDS since that is the size of the array.
int readDictionary(istream &dictfile, string dict[])
{
    string line;
  
    if(getline(dictfile, line))
    {
        *dict = line;
        return 1 + readDictionary(dictfile, dict + 1);
    }
  
    return 0;
}

// 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[])
{
    int count = 0;
  
    findPermutations("", word, dict, size, results, count);
  
    return count;
}

void findPermutations(string prefix, string rest, const string dict[], const int& size, string results[], int& count)
{
    if (rest.length() == 0)
    {
       cout << prefix << endl;
        count += checkDict(prefix, dict, size, results, &results[count], count);
    }
    else
        permu_loop(0, static_cast<int>(rest.length()), prefix, rest, dict, size, results, count);
}

void permu_loop(int i, int max, string prefix, string rest, const string dict[], const int& size, string results[], int& count)
{
    if(i >= max)
        return;
  
    findPermutations(prefix + rest[i], rest.substr(0, i) + rest.substr(i+1), dict, size, results, count);
  
    permu_loop(i + 1, max, prefix, rest, dict, size, results, count);
}

int checkDict(string target, const string dict[], int size, string results[], string result_spec[], int& count)
{
    if(size == 0)
    {
        return 0;
    }
  
    if(target == *dict)
    {
        if(isDuplicated(target, results, 0, count))
           return 0;
        else
        {
            *result_spec = target;
            return 1 + checkDict(target, dict + 1, size - 1, results, result_spec + 1, count);
        }
    }
    else
        return checkDict(target, dict + 1, size - 1, results, result_spec, count);
}

bool isDuplicated(string target, string results[], int start, int max)
{
    if(start >= max)
        return false;
  
    if(target == *results)
        return true;
    else
        return isDuplicated(target, results + 1, start + 1, max);
}

// Prints size number of strings from results.
// The results can be printed in any order.
void recurPrint(const string results[], int size)
{
    if(size == 0)
        return;
    else
    {
        cout << "Matching word " << *results << endl;
        recurPrint(results + 1, size - 1);
    }
}

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.