Ciao a tutti!

Ho dei dubbi sulla ricorsione, non tanto sulla loro applicazione all'interno del codice ma più riguardo il suo funzionamento intrinseco.

Riporto un esempio qui sotto; in questo caso l'esercizio richiede di fornire tutte le possibili permutazioni di una stringa s (presa senza caratteri ripetuti). Non mi è chiaro in questo caso quale sia il contenuto della lista lst2, che in questo caso facendo un return lst2, mi restituisce solo l'ultimo carattere della stringa quando pensavo mi restituisse l'intera lista delle permutazioni della stringa s[1:].

Spero di essere stata chiara e vi ringrazio in anticipo!

def recursivePermutation(s):
if len(s) == 0:
return []
if len(s) == 1:
return s
lst = []
c = s[0]
lst2 = recursivePermutation(s[1:])

for ss in lst2 :
for i in range(len(ss)+1):
lst.append(ss[:i] + c + ss[i:])
return lst

Uhm, non ho capito... devi fare un esercizio e stai cercando di capire come funziona la soluzione di qualcun altro? Ma non faresti prima a cercare la soluzione tu stessa? Poi quel codice è scritto maluccio, si fa capire poco in ogni caso.


Se vuoi capire come funziona il codice, dovresti capire prima con carta e penna (proprio così) come funzionerebbe la ricorsione in questo caso.


L'idea è che a ogni livello di ricorsione tu estrai un elemento della lista per volta (diciamo il primo), e lo inserisci in ogni posizione delle liste ottenute dalle permutazioni fatte sugli elementi restanti. Il tutto finché non resti con un solo elemento. Per esempio, se fosse solo il primo livello della ricorsione (ovvero, una funzione piatta, non ricorsiva), sarebbe:

>>> def perm(s):
...   res = []
...   first = s[0]   # il primo elemento, da estrarre
...   others = s[1:] # gli elementi rimanenti
...   for i in range(len(others)+1):
...     res.append(others[:i] + first + others[i:])
...   return res
...
>>> perm('Ciao')
['Ciao', 'iCao', 'iaCo', 'iaoC']

e questo è un pezzo del lavoro che fa quel codice. Il resto del lavoro sarebbe chiamare la stessa funzione, ricorsivamente, su "others" (cioè gli elementi restanti); inoltre, inserire una clausola "di arresto" per cui se gli elementi restanti sono solo più uno, allora restituisci direttamente quello senza più chiamare ricorsivamente la funzione. E vedi che ottieni un codice equivalente a quello da cui sei partita.





(detto questo, poi, se permetti resto con i miei dubbi: ieri cercavi di stampare una matrice 3x3, oggi sei passata alla ricorsione. La mia raccomandazione sarebbe sempre di seguire un buon libro, passo passo, con pazienza. Ma insomma, saprai tu).



--- Ultima modifica di RicPol in data 2019-02-03 21:58:26 ---

Ti ringrazio per la risposta, chiarissimo come sempre.

Però mi rimane un dubbio sulla creazione della lst2 con la ricorsione... secondo quale metodo si crea lst2?

Se ad esempio utilizzo cane come stringa la lst2 che mi si viene a formare è

lst2 = [ane, nae, nea, aen, ean, ena]

Perché?




PS: purtroppo non ho tempo di seguire un libro al momento, sto cercando di ottenere un'infarinatura generica

> Però mi rimane un dubbio sulla creazione della lst2 con la ricorsione... secondo quale metodo si crea lst2?


Cioè, ti rimane il dubbio di non aver capito niente dell'esercizio. Te l'ho spiegato: nel codice originale, "lst2" è ciò che si ottiene chiamando la stessa funzione sugli elementi restanti nel livello attuale della ricorsione. Davvero, devi provare con carta e penna.


> PS: purtroppo non ho tempo di seguire un libro al momento, sto cercando di ottenere un'infarinatura generica

La mia impressione del tutto personale è che tu stia ottenendo una confusione generica. In ogni caso, guarda che la ricorsione non è "infarinatura generica", è una Cosa Difficile specialmente se non ci sei abituata (perché magari la sai già fare in altri linguaggi). Se vuoi *davvero* risparmiare tempo, visto che dici che non hai tempo, io ti suggerirei di seguire un buon libro passo-passo. Ma è la mia opinione personale, poi saprai tu.