Exit Rekursion nach dem ersten Wort Übereinstimmung

Question

Diese Funktion ist entworfen, um ein falsch geschriebenes Wort zu nehmen und zu permutieren, jede vollständige Permutation gegen eine Liste von Wörtern zu prüfen, bis es eine Übereinstimmung findet.

Sobald eine Übereinstimmung gefunden wurde, soll die Funktion das übereinstimmende Wort beenden und sofort zurückgeben, ohne weiter zu permutieren.

In seinem aktuellen Zustand funktioniert die Funktion, aber es wird weiter vertauscht und gefunden, bis alle Permutationen abgeschlossen sind.

Die Funktion find() kann als ein schwarzes Feld betrachtet werden, das wahr zurückgibt, wenn das Wort mit einem Wort im dcnV-Vektor übereinstimmt, und falsch, wenn dies nicht der Fall ist. Diese Funktion funktioniert ordnungsgemäß.

dcnV: Ein Vektor von Strings, der eine Liste von Wörtern aus dem Wörterbuch enthält.

pos: Vom Rekursionsalgorithmus verwendete Ganzzahl.

p []: Lösungsmatrix.

verwendet []: Array, das verfolgt, welche Indizes in der aktuellen Permutation verwendet wurden.

Wort: ein Wort, das von der aufrufenden Funktion (kommt aus einer Textdatei) in diese Funktion übergeben wurde.

string permute (vector <string> dcnV , int pos , int p [] , 
    int used [] , string & word) 
{ 
    string tgt = word; //sets tgt to have the same size as word 

    unsigned int n = word.size(); //determines for loop range 
    unsigned int i = 0; //iterator 

    /* base case: when the end of the array is reached, 
    * map tgt to word using p array indexes 
    * search dictionary vector dcnV for matching word 
    * if found, return tgt 
    */ 
    if (pos == n && p [0] == 0 && p [n - 1] == n - 1) 
    { 
     for (i = 0; i < n; i++) 
     { 
      tgt [i] = word [p[i]]; 
     } 

     if (find (dcnV , tgt)) 
     { 
      cout << "\n Found matching word: " << tgt; 
      return tgt; 
     } 
    } 

    // recursive permutation algorithm. this is functioning correctly 
    for (i = 0; i < n; i++) 
    { 
     if (used [i] == 0) 
     { 
      p [pos] = i; 
      used [i] = 1; 
      permute (dcnV , pos + 1 , p , used , word); 
      used [i] = 0; 
     } 
    } 

    // if end of fn is reached without match, return tgt with '*' appended in 
    // front 
    return "*" + word; 
} 

versuchten Lösungen, die nicht funktionieren:

eines statischen Vektors unter Verwendung timmender Wörter zu halten, und dann Rückführen des ersten Elements dieses Vektors nur.

Setzen eines Flags, wenn ein Wort gefunden wird, und Hinzufügen einer Logikprüfung am Anfang der Funktion, die sofort zurückkehrt, wenn das Flag gesetzt ist.

setjmp, longjmp, exit, break und Ausnahmen können nicht verwendet werden.

Answer 1

bitte -std=c++11 verwenden, um zu kompilieren, oder kopieren Sie einfach permute Funktion

#include <iostream> 
#include <vector> 
#include <string> 
#include <algorithm> 
using namespace std; 

bool find(vector<string> &vs, string &s) { 
    // or use std::find, but you provide a wrong parameters 
    for (int i = 0; i < vs.size(); i++) { 
    if (vs[i] == s) return true; 
    } 
    return false; 
} 

string permute (vector <string>& dcnV , int pos , int p [] , 
       int used [] , string & word) 
{ 
    string tgt = word; //sets tgt to have the same size as word 

    unsigned int n = word.size(); //determines for loop range 
    unsigned int i = 0; //iterator 

    /* base case: when the end of the array is reached, 
    * map tgt to word using p array indexes 
    * search dictionary vector dcnV for matching word 
    * if found, return tgt 
    */ 
    // if (pos == n && p [0] == 0 && p [n - 1] == n - 1) 
    // { 
    // when pos == n, we should terminate this recurve immediately 
    if (n == pos) { 
    for (i = 0; i < n; i++) 
    { 
     tgt [i] = word [p[i]]; 
    } 

    if (find (dcnV , tgt)) 
    { 
     cout << "\n Found matching word: " << tgt << endl; 
     return tgt; 
    } else { 
     return ""; 
    } 
    } 

    // recursive permutation algorithm. this is functioning correctly 
    for (i = 0; i < n; i++) 
    { 
    if (used [i] == 0) 
    { 
     p [pos] = i; 
     used [i] = 1; 
     string t = permute (dcnV , pos + 1 , p , used , word); 
     // we have found a solution, return now 
     if (t != "") return t; 
     used [i] = 0; 
    } 
    } 

    // if end of fn is reached without match, return tgt with '*' appended in 
    // front 
    // suppose you do not search an empty string... 
    return ""; 
} 


int main(int argc, char ** argv) { 
    vector<string> vs = {"abcd", "asdf", "qqwer", "werq"}; 
    string word = "reqw"; 
    string word_nonexist = "asdsaf"; 

    int p[100] = {0}; 
    int used[100] = {0}; 

    string t1 = permute(vs, 0, p, used, word); 
    string t2 = permute(vs, 0, p, used, word_nonexist); 
    // cout << t <<endl; 

    return 0; 
}