[C++] ricorsione - generazione di combinazioni di parole

[h1jack3r]

Ciao a tutti,

con la ricorsione sono sempre stato abbastanza negato, e mi sono imbattuto un questo problema che non sono capace di risolvere...


Ho una lista di parole tutte della stessa lunghezza (le posso leggere da file e creare vari vector con le varie lunghezze)
Per l'esempio diciamo che sono tutte di lunghezza tre lettere:

Volevo, tramite procedura ricorsiva, generare tutte le varie combinazioni di ordine tra le varie stringhe:

esempio:

vector<string> dictionary;
dictionary.push_back("cat");
dictionary.push_back("far");
dictionary.push_back("ate");


in output dovro' poter avere:

cat,far,ate
cat,ate,far
far,cat,ate
far,ate,cat
ate,cat,far
ate,far,cat



Per fare cio' ho messo una funzione che si chiama backtrack() (che fantasia)
che pero' non fa quello che mi aspetto:



int rows = 3;
int backtrack(vector<string> &dictionary, vector<string> &solution, int current_row)
{
cout << "current row: "<< current_row << " of: " << rows << endl;
if(current_row == rows) //
{
return 0;
}

vector<string>::iterator word;
for(word = dictionary.begin(); word != dictionary.end(); ++word)
{

solution.push_back(*word);
backtrack(dictionary,solution,current_row+1);
}

return 1;
}



Una volta che saro' riuscito a far questo potro' aggiungere delle condizioni e chiamare la procedura ricorsiva solamente se la parola che voglio inserire soddisfa certi criteri, per poter poi alla fine creare una lista di parole che rispettano certi criteri.

Prima pero' devo risolvere questo problema, non gestisco bene il vettore delle soluzioni, e' un errore metterlo globale?
Il problema e' similare a quello delle 8 regine, solamente mi pianto con la ricorsione.


Mi sapreste dare un aiuto, o indirizzarmi verso la giusta direzione?

Grazie!

[Supdario]

Non serve passare l'indirizzo dei vector, in quanto vengono già passati per riferimento di default.

[h1jack3r]

Non serve passare l'indirizzo dei vector, in quanto vengono già passati per riferimento di default.

Ciao, grazie di averci dato un'occhiata.
Quindi posso semplicemente chiamare
backtrack(current_row+1);

comunque credo che il problema sia piu' logico, come salvo e stampo il vettore delle soluzioni?

:-)

[tuccio`]

in realtà è molto più simile a un problema di permutazioni (qui (http://twiki.di.uniroma1.it/pub/Algoritmi2/WebHome/DISP_BT.pdf) c'è un esempio in pseudocodice a pagina 2 del pdf)

nota la funzione del vettore elem in quell'esempio, che dice se nella soluzione che stai costruendo hai già usato un elemento (in quel caso gli elementi sono i numeri, per te sono le stringhe)

ps: per le soluzioni.. potresti costruire mano mano una stringa (che quindi dovresti passare alle chiamate ricorsive) e aggiungerla al vettore alla fine, nel caso base

[h1jack3r]

in realtà è molto più simile a un problema di permutazioni (qui (http://www.hwupgrade.it/forum/newreply.php?do=newreply&noquote=1&p=34379349) c'è un esempio in pseudocodice a pagina 2 del pdf)

nota la funzione del vettore elem in quell'esempio, che dice se nella soluzione che stai costruendo hai già usato un elemento (in quel caso gli elementi sono i numeri, per te sono le stringhe)


Ciao,

il link che hai messo non e' valido :-/
si e' un problema di permutazioni ma di parole e non di lettere.
Lo ho messo secondo quella formula perche' poi dovro' aggiungere delle condizioni. Ad esempio considerare solo certe parole che soddisfano i miei criteri:


In pseudocodice:

backtrack()
if(solution_valid)
return
else
for each word in dictionary
if(possible_candidate)
backtrack(n+1)


non ho ben chiaro pero' come salvare l'array delle soluzioni :-)

[tuccio`]

pardon, ho corretto il link.. non so cosa avessi copiato prima

se vuoi un vector di string come soluzione, puoi aggiungere come argomento della funzione la stringa che stai costruendo, inizialmente gli passi la stringa vuota

nel passo generico, quando fai variare l'elemento che prendi, concateni alla stringa che stai costruendo il "pezzo" scelto e chiami ricorsivamente

finita la chiamata elimini il pezzo che hai concatenato e continua il ciclo

nel caso base aggiungi la stringa al vettore

[h1jack3r]

pardon, ho corretto il link.. non so cosa avessi copiato prima

se vuoi un vector di string come soluzione, puoi aggiungere come argomento della funzione la stringa che stai costruendo, inizialmente gli passi la stringa vuota

nel passo generico, quando fai variare l'elemento che prendi, concateni alla stringa che stai costruendo il "pezzo" scelto e chiami ricorsivamente

finita la chiamata elimini il pezzo che hai concatenato e continua il ciclo

nel caso base aggiungi la stringa al vettore



scusa ma non e' proprio chiaro... se ti viene facile riusciresti a scrivermi il prototipo della funzione ricorsiva e la chiamata?

Puoi vedere qui l'output della mia attuale soluzione e vedere che efettivamente e' sballato :-)

http://www.ideone.com/ohdhb

[tuccio`]

int backtrack(const vector<string> &dictionary, vector<string> &solution, string &str, int current_row, bool *used);


io la farei (in realtà l'ho fatta :asd:) così

in cui used è un vettore che ha la funzione che ha ELEM nel pdf di prima, mentre la stringa str è la soluzione che stai costruendo.. inizialmente è una stringa vuota

ad ogni chiamata ricorsiva si prende un elemento non ancora usato, si concatena alla stringa che stai costruendo e si chiama ricorsivamente incrementando la riga corrente.. a chiamata ricorsiva ultimata si ripristina il tutto, cioè si cancella l'ultima cosa concatenata alla stringa (esattamente come si fa nel pdf per le permutazioni)

l'unica cosa che non ho capito è se vuoi che le stringhe rimangano separate, cioè se vuoi

"catfarate"
o "cat", "far", "ate"

nel secondo caso ti consiglierei di usare un vector<vector<string>> per le soluzioni, e invece di concatenare le stringhe fai il push nel vettore

ovviamente nel "caso base" fai il push della soluzione che hai costruito nel vettore delle soluzioni

ps: ah ora ho capito che vuoi fare, allora non avevo capito prima

allora l'errore è qui


for(word = dictionary.begin(); word != dictionary.end(); ++word)
{
backtrack(dictionary,solution,current_row+1);
solution.push_back(*word);


}


intanto perché fai il push dopo la chiamata ricorsiva, e devi farlo prima
e poi perché dopo la chiamata ricorsiva dovresti riportare allo stato precedente, cioè

solution.push_back(*word);
backtrack(dictionary,solution,current_row+1);
solution.pop_back();


inoltre non dovresti aggiungere ogni parola, se vuoi fare una permutazione, ma devi controllare di non aver già usato quella stringa e sceglierne una non ancora usata

pps:

allora visto che quello che avevo capito io era sbagliato, ma assomiglia al tuo, comunque ti incollo quello che avevo scritto, visto che non è proprio la soluzione al tuo problema, ma magari puoi capire cosa intendo quando dico che una stringa non sia già stata utilizzata


#include <string>
#include <iostream>
#include <vector>

#define rows 3

using namespace std;

int backtrack(const vector<string> &dictionary, vector<string> &solution, string &str, int current_row, bool *used)
{
if(current_row == rows)
{
solution.push_back(str);
return 0;
}

string str_aux = str;
for(int i = 0; i < dictionary.size(); i++)
{
if (used[i])
continue;
used[i] = true;
str += dictionary[i];
backtrack(dictionary, solution, str, current_row + 1, used);
str = str_aux;
used[i] = false;
}

return 1;
}

int main()
{
vector<string> dictionary;
dictionary.push_back("cat");
dictionary.push_back("far");
dictionary.push_back("ate");
dictionary.push_back("tea");
dictionary.push_back("fag");
dictionary.push_back("fur");
dictionary.push_back("par");
dictionary.push_back("cog");
vector<string> solution;
string s;
bool used[8] = { false };
backtrack(dictionary, solution, s, 0, used);
for (vector<string>::iterator it = solution.begin(); it != solution.end(); it++)
cout << *it << endl;
return 0;
}

[h1jack3r]

grazie mille, ho finalmente capito.


solution.push_back(*word);
backtrack(dictionary,solution,current_row+1);
solution.pop_back();



effettivamente e' qui che mi piantavo nell'uso del vettore delle soluzioni. :)

Domani leggo meglio il tuo codice, anche se fa cose diverse e' sempre utile e potro' capire qualcosa di piu'.

danke!