Esercizio 5 seconda simulazione d'esame

Question

def es5(parola):
    '''
    Es 5: 6 punti
        
    Si definisca la funzione ricorsiva (o che usa una vostra funzione ricorsiva)  
    es2(parola), che presa in input una stringa di caratteri  parola restituisce la lista delle  
    diverse "sottoparole crescenti"  di parola. Le sottoparole devono comparire nella lista in ordine lessicografico.
    Si ricorda che una sottoparola e' quello che si ottiene da una parola concellandone 0 o piu'
    caratteri (in testa, in coda o nel mezzo).
    Inoltre una sottoparola si dice crescente se i caratteri che la compongono
    letti da sinistra  a destra risultano ordinati lessicograficamente.
    
    Ad esempio  la lista restituita da es5('zanzara') sara'
    ['a', 'aa', 'aaa', 'aar', 'an', 'anr', 'anz', 'ar', 'az', 'n', 'nr', 'nz', 'r', 'z', 'zz']
    '''
    # inserisci qui il tuo codice

Idee per risolverlo? 

Answer 1

Caso base se la parola ha una lettera, ritorna {lettera}. Caso ricorsivo: crei un insieme, per ogni lettera la togli creando così una sottoparola, la aggiungi all'insieme e lo espandi con tutte le sottoparole di quella sottoparola. Ritorni l'insieme finale ottenuto dalle sottoparole di parola e dalle sottoparole di tutte le sottoparole di parola. Prima di chiamare la ricorsione controlli che quella sottoparola non sia già presente nell'insieme, sennò crei ripetizioni e ci mette troppo

Comments

con l'algoritmo che ho trovato sul diario delle lezioni non riesco a visualizzare il risultato degli ultimi due test (troppo lento), @_andrea_ puoi postare il tuo algoritmo?

---

Scambiarsi codice è vietato, non so se vale anche in questo caso però. Comunque l'ho spiegato già abbastanza bene: come caso base metto se la parola ha una lettera, altrimenti creo un insieme di tutte le sotto parole che si ottengono levando una lettera e chiamo ricorsivamente su ogni parola, ampliando l'insieme con il risultato e controllando sempre se la parola su cui chiamo la funzione non sia già presente nell'insieme di parole controllate (che è diverso da quello delle sottoparole)

---

per aggiornare l'insieme usi .update()? se ho capito bene quindi la chiamata ricorsiva va messa dentro l'update, una cosa del genere insieme.update(es5(nuovaparola)), e il controllo su cosa lo fai? su questa 'nuovaparola' che non deve essere nell'insieme risultante finale ? P.S: nuovaparola sarebbe una delle parole che si ottiene levando una lettera dalla parola precedente

---

Intanto come parametro ho anche l'insieme dee parole su cui ho chiamato già la ricorsione, inizialmente vuoto. Ogni volta che chiamo la ricorsione ci aggiungo la parola su cui l'ho chiamata. Per aggiornarlo faccio insieme|=ricorsione

---

perfetto grazie