[Algoritmi] Togliere la ricorsione [c++] [RISOLTO VIC+APA!]

[Giova411]

Testo nascosto, fai click qui per vederlo

Sarà pure OT ma, dietro i Grandi Maestri, c'é sempre una grande umanità.
Grazie per l'incoraggiamento Grande APA

Testo nascosto, fai click qui per vederlo

Codice:

int dfs(string s, int n, vector < string >&D, vector <int> &M, string i, int k, int modi){
  if (D.size() == modi)
    M[n] = M[n] + 1;
  for(int j=0; j< D.size(); j++){
     int cur = (k-1);
     if( (s.substr(cur, D[j].size())==D[j]))
        dfs(s, n, D, M, i + D[j], cur+D[j].size()+1,j+1);  //ANCORA LA RICORSIONE QUINDI E' UNA MER.....INA
   }
return M[n]; // Stampa OK il num di modi ma VIC mi mena perché fa pietà (faccina cry)
}

E' ufficiale che non riesco a togliere la ricorsione! E' ufficiale! Uscirà sul prossimo Gazzettino!

[vict85]

Sono a Roma e in questi giorni non ho accesso ad un compilatore. Comunque provo a descrivertelo a parole. Il dizionario lo metto per semplicità in un vector<string> D. La parola è in string P. Crei quindi un vector<int> M(P.lenght()+1,0) e poni M[0]=1.
A questo punto fai un ciclo for(int i=1; i<= P.lenght(); ++i) e dentro questo calcoli M[i]. Il calcolo lo fai con un ciclo sulle parole in D in cui controlli che M[i-D[j].lenght()]!=0 (e che l'indice non diventi negativo) e poi con un ciclo compari D[j][k] con P[i-1-D[j].lenght()+k]. Se il confronto ha successo aumenti M[i] di uno e passi alla prossima parola del dizionario.
Calcolato M[i] per tutte le i, restituisci al main M[P.lenght()].

[Giova411]

Testo nascosto, fai click qui per vederlo

VIC TI PAGO IL BIGLIETTO ALLORA!!! TORNAAAAA

Gli indici mi incasinano MI SENTO STUPIDOOOOOOOOOOO
Forse ho capito male, così "a parole", ma fai 3 cicli per togliere la ricorsione "stupida" mia?
Col for lavori sulla stringa, con un while (immagino) scorri il vector delle primitive
K e J come le inizializzi? CHE PALLEEEEEEE

[vict85]

Io non ho eliminato la ricorsione dalla tua, ho proposto un algoritmo che usa la memoization (o era la programmazione dinamica non ricordo bene la differenza). L'eliminazione della tua ricorsione non è comunque semplicissima perché ogni funzione ricorsiva contiene un ciclo al suo interno.

Comunque ho usato un compilatore online e sembra che questo funzioni.

Codice:

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

using namespace std;

int dfs(vector<string> &D, string P);

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;
  cout << "Numero: " << dfs(P, X) << endl;
}

int dfs(vector<string> &D, string P)
{
   int const Ps = P.length();
   vector<int> M(Ps+1, 0);
   M[0] = 1;
   
   for(int i=1; i<= Ps; ++i)
   {
      int const Ds = D.size();
      for(int j=0; j < Ds; ++j)
      {
         int const Djs = D[j].length();
         if(Djs <= i)
         {
            if(M[i - Djs] != 0)
            {
               int k = 0;
               for(; (k < Djs)&&(D[j][k] == P[i-Djs+k]); ++k);
               if(k == Djs)
                  M[i] += M[i - Djs];
            }
         }
      }
   }
   return M[Ps];
}

anche se immagino sarebbe necessario qualche test più serio per esserne sicuri (ho usato il tuo codice per il main).


Ripensando alle questioni relative all'ordinamento non sono sicuro che valga troppo la pena farlo. Per problemi semplici probabilmente non ci sono neanche così tanti vantaggi a non usare la ricorsione.

[Giova411]

Mi sento "CONFUSA E FELICE"
Vic scrivi il codice bene, davvero ti invidio!!!!!!!!
In questo caso non son riuscito a farlo "bene" su "carta e penna", figuriamoci a farlo efficente col codice.
Come dice APA bisogna allenarsi con queste "coding interview", ma anche avere la padronanza del linguaggio come Vic.
Ad esempio, solo ora, ho visto come usare bene un vector a tal punto da poter scrivere " D[j][k] "... GRAZIE VIC DAVVERO (una finezza, tipo quei doppi-passi di Ronaldo nel 1997/'98.. e non sono interista!).

Io non ho eliminato la ricorsione dalla tua, ho proposto un algoritmo che usa la memoization (o era la programmazione dinamica non ricordo bene la differenza)

Da quel che ricordo, una è sottoinsieme dell'altra; ossia la memo è una PD "tirchia" perché "prende nota" solo dei dati che servono e non di tabelle piene riempite tutte senza badare al consumo di spazio. Se la memoized prende troppi appunti allora sfocia in una PD(credo)
Nel codice mio (che faceva andar di corpo anche la nonna mia stitica dal 1988) non c'era nessuna memo ed una ricorsione grande come l'Empire State Building...

Prima di chiudere con un "risolto" PENSATE si possa dire che la soluzione di VIC sia O( nm ) ?
Si può fare di meglio? Dai aspettiamo che torni dalla Capitale!!!!!

[vict85]

Se con m si intendi il numero di caratteri che compongono complessivamente D allora si. Altrimenti è più un O(mnp) dove p è la lunghezza massima delle primitive. Il metodo di apatriarca (che di c++ e programmazione ne sa sicuramente più di me¹) è lineare su n ma richiede di trovare l'automa (a meno che non si conoscano le primitive in anticipo). Devo dire che essendo un matematico e non un informatico non ho mai esplorato gli algoritmi per la creazione di automi e la loro complessità. Se m e p sono piccoli rispetto a n probabilmente conviene, per m e p grandi dipenderà dall'algoritmo per farlo.

---

Note

1. Ed essendo mio fratello gemello posso dirlo con una certa sicurezza. ↑

[Giova411]

AH DICEVO IO!!!!! GENI BUONI!!! CHE FORTUNA!!!!!!!
Per un attimo, all'inizio, ero sicuro che Apa mi sparasse un codice di 4 righe perfetto ma in Python

Sì è vero!!!!! E' O(nmp)!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Quindi meglio di quello che hai proposto te non è possibile!!!!!!!
GRAZIE A LOT!!!!!

Spero di trovare altri problemi simili!

[apatriarca]

Si può costruire un automa se si vuole ottenere qualcosa di meglio di quello che ho descritto in un mio precedente post, ma quella descrizione non conteneva alcun automa. Nota che in pratica l'idea viene dal fatto che il tuo problema originale (senza il conteggio del numero di combinazioni) è equivalente a chiedersi se la stringa rispetta la regex (AB|BA|ABB|BAB)*. Questa regex può ovviamente essere migliorata nella forma che avevo scritto. Siccome esiste un algoritmo per fare questo test in tempo lineare (non tutte le librerie regex usano questo algoritmo perché hanno funzionalità più avanzate per cui l'algoritmo non è applicabile), esiste un algoritmo in tempo lineare sulla lunghezza della stringa per risolvere anche il tuo problema.

[Giova411]

Quando scrivi faccio questo ->
Dopo vedo meglio di cosa parli
Quel simbolo " | " lo ricordo quando studiai Calcolo delle Prob (tipo 10 anni fa... )
Forse vedi una sorta di dag ed avanzi solo quando c'é una primitiva?


BUONGIORNO A TUTTI MITI MIEI!

[apatriarca]

No, parlo di Regular Expression.. Se non le conosci ti consiglio di darci un'occhiata perché sono utili in molti contesti. La barra verticale significa che devi prendere in considerazione l'espressione a sinistra oppure quella a destra. Quindi (AB|BA) significa "AB" oppure "BA". Nel link vedi anche altre operazioni. Se guardi la parte relativa all'implementazione, vedrai che si fa riferimento ad algoritmi lineari basati su automi (DFA o NFA) e poi un algoritmo basato sul backtracking. Per una descrizione più dettagliata dell'algoritmo che ho in mente puoi dare una occhiata a questo link. Discute l'implementazione (in C) di una funzione per il matching di espressioni regolari. È più generale e un po' diverso rispetto al tuo problema, ma è da dove ho preso l'idea.