[Algo] Esercizio2 BackTracking

[Pablitos23]

Dare lo pseudo-codice di un algoritmo che, preso in input un intero n, stampi tutte le stringhe di lunghezza n sull'alfabeto {a, b, c} tali che il numero di occorrenze di a è minore o uguale al numero di occorrenze di b che a sua volta è minore o uguale al numero di occorrenze di c. Ad esempio se n = 3 allora l'algoritmo deve produrre (non necessariamente in quest'ordine): ccc, bcc, cbc, ccb, abc, bac, bca, acb, cab e cba. La complessità dell'algoritmo deve essere O(nS(n)), dove S(n) è il numero di stringhe da stampare.

Questo sembra essere più facilotto:

A: contatore occorrenze per ogni lettera
S: stringa
n: lunghezza totale
h: lunghezza stringa generata

GenS( n , h , S , A )
   if n==h then OUTPUT S
   else
       for i<-1 to n
          for y in {a,b,c}
             A[y] <- A[y] + 1
             if ( isSafe( A , S ) ) then
                  S[h+1] <- y
                  GenS( n, h+1, S, A )
            else
                 A[y] = A[y] - 1

Mi manca lo pseudocodice di isSafe, la quale funzione ritorna true se i vincoli sono soddisfati, false altrimenti. Può andare come ho impostato l'algoritmo utilizzando la tecnica del BackTracking??

Grazie.

[apatriarca]

C'è una ragione per cui non scrivi mai lo pseudocodice di isSafe?

[Pablitos23]

Penso di no. Tra poco scrivo entrambi le isSafe.

Grazie per l'aiuto.

[Pablitos23]

Qua la funzione di controllo dei vincoli per il tagliare lo spazio di ricerca isSafe non sembra essere molto complessa.

isSafe(A: array contatore occorrenze) -> boolean
    return A[1] <= A[2] and A[2]<=A[3];

Può prendere in pasto solo l'array che conta il numero di occorrenze delle lettere {a,b,c} nella stringa e non come ho scritto su.

E' giusta??
L'unica cosa è che non risco a capirne se la complessità è un O(nS(n)).

[apatriarca]

Per prima cosa direi che potrebbe essere utile capire quanto valga \(S(n)\).. Qual'è la complessità del tuo algoritmo?

[Pablitos23]

S(n) sarà un $O(3^n)$ con n=numero di lettere, ma la stima è approssimativa dato che non ho calcolato i tagli sullo spazio di ricerca, ovvero tutte le stringhe che non vengono generate perchè non rispettano i vincoli.

Mentre $Theta(n)$ è il ciclo for esterno.

Quindi complessivamente $O(nS(n))$.

E' una stima troppo lasca il primo $3^n$?