[Algoritmi] Togliere la ricorsione [c++] [RISOLTO VIC+APA!]
Volevo esercitarmi per diletto e per non perdere la "mano"... 
Anche perché questi sono esercizi classici nelle prove d'assunzione alla google, amazon e compagnia bella..
Avevo visto un esercizio del forum (IN STILE STRINGHE DEL DNA da confrontare) e pensavo di farlo ma è rimasto bloccato lì.
Consideriamo un dizionario con delle stringhe date ad esempio di 4 come questo:
AB BA ABB BAB
Data poi una stringa casuale come questa:
ABBBABABAB
Bisogna trovare se quest'ultima data è composta dalle sole stringhe del dizionario (anche ripetute)
Nell'esempio dovrei ottenere 3 modi possibili
(ossia tre modi: ABB − BA − BA − BAB, oppure ABB − BA − BAB − AB e ABB − BAB − AB − AB )
Sempre con lo stesso dizionario, ma dando una stringa diversa tipo questa:
ABBAAAB
Ottengo 0 modi.
Un codice ricorsivo che funziona l'ho scritto ma volevo sfruttare la programmazione dinamica o, per strafare, la tecnica memoization che memorizza solo cio' che ci serve.
Sono tornato a rompere
Anche perché questi sono esercizi classici nelle prove d'assunzione alla google, amazon e compagnia bella..
Avevo visto un esercizio del forum (IN STILE STRINGHE DEL DNA da confrontare) e pensavo di farlo ma è rimasto bloccato lì.
Consideriamo un dizionario con delle stringhe date ad esempio di 4 come questo:
AB BA ABB BAB
Data poi una stringa casuale come questa:
ABBBABABAB
Bisogna trovare se quest'ultima data è composta dalle sole stringhe del dizionario (anche ripetute)
Nell'esempio dovrei ottenere 3 modi possibili
(ossia tre modi: ABB − BA − BA − BAB, oppure ABB − BA − BAB − AB e ABB − BAB − AB − AB )
Sempre con lo stesso dizionario, ma dando una stringa diversa tipo questa:
ABBAAAB
Ottengo 0 modi.
Un codice ricorsivo che funziona l'ho scritto ma volevo sfruttare la programmazione dinamica o, per strafare, la tecnica memoization che memorizza solo cio' che ci serve.
Sono tornato a rompere
Risposte
Il codice che ho ideato che non funziona ma non trovo il bug.. Ma sento che la soluzione è ad un passo 
#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
#include <string>
using namespace std;
int dfs(string x, int n, vector < string >&S, int C[], string i, int k){
if(i.length() > x.length()) {
return 0;
}
if (i == x) {
return 1;
}
for(int j=0; j< S.size(); j++){
int cur = (k-1);
if (cur <= n && x.substr( cur,S[j].size() ) == S[j] ){
C[k] = C[k-1] + dfs(x, n, S, C, i + S[j], cur+S[j].size()+1);
}
}
return C[k];
}
int main (){
string X;
vector < string > P;
int N;//numero di primitive
cout << "Inserisci il numero di primitive: \n";
cin >> N;
string temp;
cout << "Inserisci le primitive (separate da uno spazio): \n";
for (int i = 0; i < N; i++){
cin >> temp;
P.push_back (temp);
}
cout << "Inserisci la stringa: \n";
cin >> X;
int n = X.length();
int C[n+1];
string l = "";
int k = 1;
memset(C, 0, sizeof(C));
cout << "Numero: " << dfs (X, n, P, C, l, k) << endl;
}
In questo momento non ho la possibilità di guardare il tuo codice. Volevo però dirti che non è necessario mettere il codice come spoiler. Si tratta in effetti di qualcosa di abbastanza centrale nella discussione per cui ha senso averlo visibile..
Mitico MITICOOOOOOO
(ora modifico il post, DANKE)
(ora modifico il post, DANKE)
Solo un altro piccolo commento. Se mai facessi un colloquio in cui ti chiedono di risolvere un problema di questo tipo, non strafare.. A meno che non ti venga espressamente richiesto, implementa la versione più semplice che ti viene in mente. Nella maggior parte dei casi lo scopo di questi test è quello di verificare se sai realizzare dei semplici programmi, non tanto vedere se sai arrivare ad una soluzione elegante ed efficiente. Se proprio ci tieni a far vedere che conosci anche metodi più complicati puoi sempre dirlo a voce.
Apa mi mancavi e son tornato a scrivere anche per imparare da te.
Sì, nella fattispecie, questo è un esercizio che si risolve magari con 3 cicli.
L'ho preso proprio da una discussione che avevi risolto ad Hamming cambiando però le richieste =)
L'avevo lasciato lì ma ora voglio risolverlo per SFIZIO
(spero col tuo aiuto o chiunque voglia risolvere questi PUZZLE 
)
Sì, nella fattispecie, questo è un esercizio che si risolve magari con 3 cicli.
L'ho preso proprio da una discussione che avevi risolto ad Hamming cambiando però le richieste =)
L'avevo lasciato lì ma ora voglio risolverlo per SFIZIO
(spero col tuo aiuto o chiunque voglia risolvere questi PUZZLE
)
Ci sono delle problematiche del tuo codice.
Il primo è l'aver aggiunto una libreria che neanche stai usando: cmath .
Il secondo è di aver usato i VLA in un codice C++, ovvero hai usato codice non standard. Cosa che non hai notato perché non hai messo tra le opzione del compilatore -pedantic, -Wpedantic o -Wvla-extension (insieme a -std=c++11) e il tuo compilatore, gcc immagino, possiede i VLA come estensione del C++. Tra l'altro la soluzione consigliata in campo C++ è quella di usare un vector (che stai già usando ovunque) e che avrebbe reso inutile l'uso di memset, e pertanto anche di cstring.
Penso sia inoltre importante osservare che il numero di lettere dell'alfabeto è molto ridotto (2 in questo caso, 4 nel caso del DNA). Questo permette di usare strutture dati particolari per memorizzare il dizionario in modo compatto. Penso sia inoltre utile ordinare adeguatamente il dizionario per eliminare test inutili.
Mi sembra che in generale manchino nel tuo codice dei test per eliminare i rami inutili. Insomma generati tutte le combinazioni anche se è inutile.
Il primo è l'aver aggiunto una libreria che neanche stai usando: cmath .
Il secondo è di aver usato i VLA in un codice C++, ovvero hai usato codice non standard. Cosa che non hai notato perché non hai messo tra le opzione del compilatore -pedantic, -Wpedantic o -Wvla-extension (insieme a -std=c++11) e il tuo compilatore, gcc immagino, possiede i VLA come estensione del C++. Tra l'altro la soluzione consigliata in campo C++ è quella di usare un vector (che stai già usando ovunque) e che avrebbe reso inutile l'uso di memset, e pertanto anche di cstring.
Penso sia inoltre importante osservare che il numero di lettere dell'alfabeto è molto ridotto (2 in questo caso, 4 nel caso del DNA). Questo permette di usare strutture dati particolari per memorizzare il dizionario in modo compatto. Penso sia inoltre utile ordinare adeguatamente il dizionario per eliminare test inutili.
Mi sembra che in generale manchino nel tuo codice dei test per eliminare i rami inutili. Insomma generati tutte le combinazioni anche se è inutile.
Eh si Vic ho fatto un po' di cavolate nella seconda versione.
Ad esempio memset l'avevo usata per poi toglierla e mi son dimenticato.
Era una prova da battaglia con molti cout sparsi.
Fermo rimane il primo "pensiero ricorsivo" vedi il primo codice nello spoiler.
Da lì io vorrei arrivare ad usare la tecnica memoization per non sballare troppo di entry il pc con stringhe molto più lunghe.
Il primo l'avevo scritto di botto ma la tecnica memoization (pur avendo superato bene l'esame di Algo) non l'ho mai digerita...
(come puoi immaginare anche la PD, che comprende la suddetta tecnica, non mi è mai entrata bene)
PS: Pensi al PRUNING quindi col backtrack?
Ad esempio memset l'avevo usata per poi toglierla e mi son dimenticato.
Era una prova da battaglia con molti cout sparsi.
Fermo rimane il primo "pensiero ricorsivo" vedi il primo codice nello spoiler.
Da lì io vorrei arrivare ad usare la tecnica memoization per non sballare troppo di entry il pc con stringhe molto più lunghe.
Il primo l'avevo scritto di botto ma la tecnica memoization (pur avendo superato bene l'esame di Algo) non l'ho mai digerita...
(come puoi immaginare anche la PD, che comprende la suddetta tecnica, non mi è mai entrata bene)
PS: Pensi al PRUNING quindi col backtrack?
Credo tu stia in un certo senso risolvendo il problema sbagliato. Ti viene infatti chiesto se la stringa può essere scritta con le solo sottostringhe dell'alfabeto, non di calcolare il numero di possibili modi per farlo. Cercando il numero di modi stai insomma facendo molti più calcoli del necessario. Il problema originale può essere risolto in tempo lineare. Non è affatto necessario ricorrere a tecniche come la memoization.
Consideriamo il tuo esempio. Tu hai le sottostringhe AB, BA, ABB e BAB. Ogni stringa composta da queste sottostringhe sarà quindi della forma ((AB|BA)B?)* usando le espressioni regolari.. Un metodo di risoluzione potrebbe quindi essere quello di generare un NDA (o DFA) che risolve questo problema. La versione più semplice potrebbe essere quella di mantenere un insieme di stati possibili e di aggiornare questi stati man mano che leggi la stringa. Il numero massimo di stati sarà uguale al numero di sottostringhe (ma solo se non ottimizzi l'automa). Se il numero di stati possibili arriva a zero prima di raggiungere la fine della stringa (o la stringa finisce quando nessuno degli stati è alla fine della stringa) vuol dire che la risposta è negativa. In caso contrario è positiva.
Consideriamo il tuo esempio. Tu hai le sottostringhe AB, BA, ABB e BAB. Ogni stringa composta da queste sottostringhe sarà quindi della forma ((AB|BA)B?)* usando le espressioni regolari.. Un metodo di risoluzione potrebbe quindi essere quello di generare un NDA (o DFA) che risolve questo problema. La versione più semplice potrebbe essere quella di mantenere un insieme di stati possibili e di aggiornare questi stati man mano che leggi la stringa. Il numero massimo di stati sarà uguale al numero di sottostringhe (ma solo se non ottimizzi l'automa). Se il numero di stati possibili arriva a zero prima di raggiungere la fine della stringa (o la stringa finisce quando nessuno degli stati è alla fine della stringa) vuol dire che la risposta è negativa. In caso contrario è positiva.
Io volevo contare i modi e non solo dire se è vero o falso.
Se fai partire il primo mio codice, ti dice quanti modi hai per formare la stringa in base alle stringhe del dizionario dato.
Quindi devo tornre il numero delle permutazioni. Dici si possa fare in O(n) ? Al più O(n m)
Se fai partire il primo mio codice, ti dice quanti modi hai per formare la stringa in base alle stringhe del dizionario dato.
Quindi devo tornre il numero delle permutazioni. Dici si possa fare in O(n) ? Al più O(n m)
Consideravo \(m\) costante nell'analisi.. Direi che con una piccola modifica puoi comunque restituire anche il numero di possibili combinazioni. Devi semplicemente contare quanti percorsi diversi ti hanno portato ad un particolare stato.
Questa "piccola modifica" mi sta facendo andare al manicomio APA!!! = (
Devo memorizzare i modi diversi ed ho pensato ad una DFS, cosa ne pensi?
La ricorsione la posso levare dalla cosidette o me la devo tenere?
L'array dove memorizzo il risultato, diciamo pure il C[n] per capirci, lo riempo benino (FORSE) ma poi sommo il risultato della ricorsione che "sballa" il risultato...
PS: da google me lo scordo di lavorare.....
pure se gli scrivo in pseudocodice mi menano pure 
Devo memorizzare i modi diversi ed ho pensato ad una DFS, cosa ne pensi?
La ricorsione la posso levare dalla cosidette o me la devo tenere?
L'array dove memorizzo il risultato, diciamo pure il C[n] per capirci, lo riempo benino (FORSE) ma poi sommo il risultato della ricorsione che "sballa" il risultato...
PS: da google me lo scordo di lavorare.....
pure se gli scrivo in pseudocodice mi menano pure
No.. ora sono al lavoro per cui non tempo di scrivere proprio alcuna soluzione.. Ripensandoci comunque, credo che in realtà il numero di stati possano anche essere maggiori del numero di stringhe. Ne sono anzi abbastanza sicuro (basta prendere un dizionario tipo "a, aa, aaa, aaaa"). Il numero massimo dovrebbe essere il numero di caratteri totali nel dizionario più due.
Considera i seguenti casi:
1. Da uno stato se ne possono creare due o più. Per esempio, nello stato iniziale potresti avere più di una sottostringa con la stessa iniziale. Se \(n\) è il numero di percorsi con cui sei arrivato allo stato precedente, allora devi copiare questo numero in ognuno degli stati figli successivi.
2. Più di uno stato si fondono allo stesso stato. Per esempio quando finisci più di una sottostringa. Questo nuovo stato sarà raggiungibile percorrendo un numero di percorsi uguale alla somma dei percorsi.
3. Se invece c'è uno stato che si trasforma in un altro che non è raggiunto da altri stati allora il numero di percorsi sarà costante. Per esempio se ti trovi all'interno di una singola sottostringa.
Considera i seguenti casi:
1. Da uno stato se ne possono creare due o più. Per esempio, nello stato iniziale potresti avere più di una sottostringa con la stessa iniziale. Se \(n\) è il numero di percorsi con cui sei arrivato allo stato precedente, allora devi copiare questo numero in ognuno degli stati figli successivi.
2. Più di uno stato si fondono allo stesso stato. Per esempio quando finisci più di una sottostringa. Questo nuovo stato sarà raggiungibile percorrendo un numero di percorsi uguale alla somma dei percorsi.
3. Se invece c'è uno stato che si trasforma in un altro che non è raggiunto da altri stati allora il numero di percorsi sarà costante. Per esempio se ti trovi all'interno di una singola sottostringa.
Sia
- [*:1nt46dyz] \(\displaystyle S \) la stringa ce vuoi testare.[/*:m:1nt46dyz]
[*:1nt46dyz] \(\displaystyle D \) l'elementi \(\displaystyle i \)-esimo del dizionario.[/*:m:1nt46dyz]
[*:1nt46dyz]\(\displaystyle M(i) \) il numero di modi in cui puoi scrivere la sottostringa \(\displaystyle S[0:i-1] \) con elementi del dizionario, pongo \(\displaystyle M(0)=1 \) e \(\displaystyle M(i) =0 \) per \(\displaystyle i<0 \).[/*:m:1nt46dyz]
[*:1nt46dyz] \(\displaystyle \ell \) la lunghezza della parola \(\displaystyle i \)-esima del dizionario.[/*:m:1nt46dyz]
[*:1nt46dyz] \(\displaystyle D \ominus_j S \) è la funzione che confronta \(\displaystyle D \) con le ultime \(\displaystyle \ell \) lettere di \(\displaystyle S[0:j-1] \) e restituisce \(\displaystyle 0 \) o \(\displaystyle 1 \) a seconda se sia o meno uguale.[/*:m:1nt46dyz][/list:u:1nt46dyz]
Tu vuoi conoscere \(\displaystyle M(n) \) dove \(\displaystyle n \) è la lunghezza della parola \(\displaystyle S \). Ma risulta che \(\displaystyle M(t) = \sum_i M\bigl(t-\ell\bigr)\cdot \bigl(D \ominus_j S\bigr)\). Nota che se ordini adeguatamente \(\displaystyle D \) puoi limitare i calcoli (e non dimenticarti di testare se \(\displaystyle M\bigl(t-\ell\bigr) \) è uguale a \(\displaystyle 0 \) )
Ragazzi per "digerire" le vostre dritte mi serve un po' di tempo.
Ad esempio non capisco come poter ordinare le stringhe del dizionario..
Vic tu che sei un esperto di tutti gli standard c++ cosa mi consigli?
Riscrivere da zero quello che stavo provando? (mi riferisco al secondo scritto male)
La funzione che fa il confronto di stringhe pure era cannata?
Ad esempio non capisco come poter ordinare le stringhe del dizionario..
Vic tu che sei un esperto di tutti gli standard c++ cosa mi consigli?
Riscrivere da zero quello che stavo provando? (mi riferisco al secondo scritto male)
La funzione che fa il confronto di stringhe pure era cannata?
"vict85":
\(\displaystyle M(t) = \sum_i M\bigl(t-\ell\bigr)\cdot \bigl(D \ominus_j S\bigr)\)
Vic sono così
. Questa è la somma delle chiamate ricorsive? Mettiamo tutto gradualmente in un vettore?Ma t cosa dovrebbe rappresentare nel tuo ragionamento? (Un indice che muove da sx a dx?)
Mi sto impallando troppo con sto QUIZZZ!!!!
L'idea nel mio caso era quella di scriversi una classe "Stato" fatta più o meno nel modo seguente:
struct Stato {
int num_stringa;
int pos;
int count;
};
num_stringa uguale a -1 può ad esempio rappresentare l'inizio/fine delle sottostringhe. Conviene probabilmente mantenere una stato "costante" uguale a questo inizio/fine in modo da semplificare la "fusione" degli stati. Mantieni a questo punto due vector
Ragazzi grazie per come mi aprite la mente!
Stavo seguendo l'idea di Vic che mi pare l'abbia risolto con la massima efficenza. Forse ordina pure il dizionario per lunghezza delle stringhe..
Io non ho ancora un codice buono ma diciamo che saprei "stampare" il risultato esatto grazie ad una variabile contatore ma non un vettore e non efficente per nulla...
Dopo vorrei provare l'idea di Apa che mi pare diversa...
Vic hai un codice? Ti avanza qualcosa?
Stavo seguendo l'idea di Vic che mi pare l'abbia risolto con la massima efficenza. Forse ordina pure il dizionario per lunghezza delle stringhe..
Io non ho ancora un codice buono ma diciamo che saprei "stampare" il risultato esatto grazie ad una variabile contatore ma non un vettore e non efficente per nulla...
Dopo vorrei provare l'idea di Apa che mi pare diversa...
Vic hai un codice? Ti avanza qualcosa?
E' ufficiale che non riesco a togliere la ricorsione! E' ufficiale! Uscirà sul prossimo Gazzettino!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo