Aiuto funzione ricorsiva

G
GiuseppeLaRocca (1170 points)
3 15 28
asked Apr 12, 2018 in Programmare in Python by GiuseppeLaRocca (1,170 points)
closed May 27, 2018 by andrea.sterbini
Scusate, qualcuno può aiutarmi ad approcciare questa funzione ricorsiva per un albero di parole?

- path(w1, w2):  ritorna un insieme (tipo set) che contiene tutte le tuple di
parole che corrispondono a cammini nell'albero che iniziano con un nodo con la
parola w1 e terminano con un nodo con la parola w2.

Questo è il testo dell'esercizio:

'''Partendo da una parola e da una stringa di caratteri e' possibile, a volte, formarne altre sostituendo
una lettera della parola con un'altra lettera lessicograficamente superiore presa all'interno della stringa di caratteri.
Ad esempio, partendo dalla parola "case" e dalla stringa di caratteri "ro" possiamo mutare la
"a" con la "o" ottenendo "cose", o anche la "e" con la "o" ottenendo "caso", mutando poi la "c" con la "r" nella parola
"caso" otteniamo "raso" e da questa mutando la "a" con la "o" otteniamo "roso". Possiamo dunque considerare tutte
le parole che si ottengono sostituendo una lettera della parola con una lettera
lessicograficamente successiva presente nella stringa di caratteri, ripetere la
stessa operazione a partire da quest'ultime e cosi' via ottenendo un albero di
parole.

Grazie.
206 views
closed with note: answered

1 Answer

andrea.sterbini (172780 points)
513 935 1789
answered Apr 14, 2018 by andrea.sterbini (172,780 points)
Immagino che sia per un programma di enigmistica.
E inoltre che sia presente un elenco delle parole valide (l'esempio usa solo parole valide).
G
GiuseppeLaRocca (1170 points)
3 15 28
commented Apr 14, 2018 by GiuseppeLaRocca (1,170 points)
Si, è un vecchio HW e alla creazione dell'albero utilizzo solo parole presenti in un txt;
l'unico mio problema è che non riesco ad approcciare questo 'cammino' della funzione 'path(w1, w2)'
andrea.sterbini (172780 points)
513 935 1789
commented Apr 14, 2018 by andrea.sterbini (172,780 points)
immagina l'albero
data w1 tutti i figli sono le parole che differiscono da w1 su una sola lettera che è successiva a quella di w1
per ciascuno dei figli lo stesso finchè non hai più nessuna parola

Su questo albero (implicito) puoi fare una ricerca depth-first della parola w2 e al ritorno raccogliere i percorsi
G
GiuseppeLaRocca (1170 points)
3 15 28
commented Apr 16, 2018 by GiuseppeLaRocca (1,170 points)
Perfetto, grazie.