Topic: funzione ricorsiva per permutazioni  (Letto 161 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline ortobio

  • python unicellularis
  • *
  • Post: 3
  • Punti reputazione: 0
    • Mostra profilo
funzione ricorsiva per permutazioni
« il: Novembre 30, 2020, 18:34 »
un saluto a tutti,

è da questa mattina che sto perdendo la testa su un piccolo script trovato sul libro di lutz.

def permute1(seq):
    if not seq:                               # Shuffle any sequence: list
        return [seq]                          # Empty sequence
    else:
        res = []
        for i in range(len(seq)):
            rest = seq[:i] + seq[i+1:]        # Delete current node
            for x in permute1(rest):          # Permute the others
                res.append(seq[i:i+1] + x)    # Add node at front
        return res
   
   
print(permute1('abcd'))


ovviamente non ho la pretesa che mi spieghiate passo passo come funziona ma vi chiedo se avete qualche consiglio, qualche risorsa su internet insomma qualche strumento per poter studiare e capire la logica di questo codice. grazie mille.

Offline RicPol

  • python sapiens sapiens
  • ******
  • Post: 3.146
  • Punti reputazione: 9
    • Mostra profilo
Re:funzione ricorsiva per permutazioni
« Risposta #1 il: Novembre 30, 2020, 22:11 »
guarda... onestamente non so più che cosa dire su 'sta ricorsione... Non c'è libro, corso, etc. che non rompa enormemente le p***e con la ricorsione... e la ricorsione a un certo punto sembra sempre il sacro graal del principiante... "ah, se solo capissi la ricorsione, saprei programmare di botto"...

Allora, chiariamo una volta per tutte. Conoscere una buona dose di
1) strutture-dati
e
2) algoritmi (che si appoggiano a diverse strutture-dati)
è sicuramente fondamentale per saper programmare, in qualsiasi linguaggio. Col tempo, uno si fa una sorta di biblioteca mentale di algoritmi (e di strutture-dati) che tiene "a portata di mano", e applica alla bisogna per risolvere i problemi reali della sua vita di programmatore. Non è che per forza uno debba conoscere questi algoritmi nel dettaglio... di solito basta avere una robusta consapevolezza che esistono, sapere quale tipo di problemi risolvono, e sapere dove trovare una buona implementazione di riferimento. Ma certamente, più algoritmi (e strutture-dati) si conoscono, più li si conosce nel dettaglio, meglio si sta. E' come parlare una lingua straniera, e sapere dozzine di modi di dire, frasi idiomatiche eccetera. Non c'è niente da fare, nella vita reale si vede la differenza.

Gli algoritmi ricorsivi sono una classe di algoritmi senz'altro importante (ma non certo maggioritaria), e senz'altro vale la pena di imparare qualche rudimento di ragionamento ricorsivo.

Detto questo, la ricorsione è notoriamente ostica da capire, e francamente viene buttata lì dai vari corsi,
1) un po' per far capire che il corso "è di quelli seri", su cui bisogna sudare
2) un po' perché bisogna "formare il carattere" dello studente dandogli cose astratte e difficili da fare.

Ora, siccome la ricorsione è un modo molto economico di dimostrare che il corso è serio, il risultato è che praticamente tutti i corsi buttano lì l'esercizio sulla ricorsione. Magari non ti spiegano davvero come funziona una lista e che cosa ci puoi fare... ma l'esercizio sulla ricorsione sta tranquillo che non manca mai.

Detto questo, chiariamo: se non riesci ad arrampicare il tuo cervello su un ragionamento ricorsivo, con una certa rapidità... è meglio essere onesti, qui... è come "essere portati per la matematica"... si può fare matematica anche senza esserlo, ma... c'è differenza.
D'altro canto, se non riesci a "vedere" la ricorsione *adesso*... puoi tranquillamente lasciar perdere e tornarci sopra più tardi, più volte, con calma... non è che la ricorsione deve proprio essere il macigno che ti frena per giorni... Magari se passi oltre e aspetti di conoscere più algoritmi, di esserti fatto le ossa, di aver visto e fatto molti più ragionamenti... magari poi ti viene. Certo, non puoi evitarla per sempre... ma insomma non so proprio se mi ci incaponirei adesso.


Detto tutto questo, se vuoi provare un esercizio... laterale... guarda questo: https://pythoninwindows.blogspot.com/2019/01/esercizio-funzioni-ricorsive.html
In questo articolo spiego come si ragiona per risolvere un esercizio ricorsivo. Non è lo stesso che hai tu, ma appunto... Prova a lasciar perdere il tuo esercizio per un po', prova a seguire il ragionamento del mio articolo... troverai dei punti fermi che ti possono servire per tutti gli esercizi ricorsivi... poi magari riesci a riprendere in mano il tuo esercizio, e ti viene un po' più facile.

Ma ripeto, non è che casca il mondo, se rimandi il problema un po'.

Offline ortobio

  • python unicellularis
  • *
  • Post: 3
  • Punti reputazione: 0
    • Mostra profilo
Re:funzione ricorsiva per permutazioni
« Risposta #2 il: Dicembre 02, 2020, 20:45 »
guarda... onestamente non so più che cosa dire su 'sta ricorsione... Non c'è libro, corso, etc. che non rompa enormemente le p***e con la ricorsione... e la ricorsione a un certo punto sembra sempre il sacro graal del principiante... "ah, se solo capissi la ricorsione, saprei programmare di botto"...

Allora, chiariamo una volta per tutte. Conoscere una buona dose di
1) strutture-dati
e
2) algoritmi (che si appoggiano a diverse strutture-dati)
è sicuramente fondamentale per saper programmare, in qualsiasi linguaggio. Col tempo, uno si fa una sorta di biblioteca mentale di algoritmi (e di strutture-dati) che tiene "a portata di mano", e applica alla bisogna per risolvere i problemi reali della sua vita di programmatore. Non è che per forza uno debba conoscere questi algoritmi nel dettaglio... di solito basta avere una robusta consapevolezza che esistono, sapere quale tipo di problemi risolvono, e sapere dove trovare una buona implementazione di riferimento. Ma certamente, più algoritmi (e strutture-dati) si conoscono, più li si conosce nel dettaglio, meglio si sta. E' come parlare una lingua straniera, e sapere dozzine di modi di dire, frasi idiomatiche eccetera. Non c'è niente da fare, nella vita reale si vede la differenza.

Gli algoritmi ricorsivi sono una classe di algoritmi senz'altro importante (ma non certo maggioritaria), e senz'altro vale la pena di imparare qualche rudimento di ragionamento ricorsivo.

Detto questo, la ricorsione è notoriamente ostica da capire, e francamente viene buttata lì dai vari corsi,
1) un po' per far capire che il corso "è di quelli seri", su cui bisogna sudare
2) un po' perché bisogna "formare il carattere" dello studente dandogli cose astratte e difficili da fare.

Ora, siccome la ricorsione è un modo molto economico di dimostrare che il corso è serio, il risultato è che praticamente tutti i corsi buttano lì l'esercizio sulla ricorsione. Magari non ti spiegano davvero come funziona una lista e che cosa ci puoi fare... ma l'esercizio sulla ricorsione sta tranquillo che non manca mai.

Detto questo, chiariamo: se non riesci ad arrampicare il tuo cervello su un ragionamento ricorsivo, con una certa rapidità... è meglio essere onesti, qui... è come "essere portati per la matematica"... si può fare matematica anche senza esserlo, ma... c'è differenza.
D'altro canto, se non riesci a "vedere" la ricorsione *adesso*... puoi tranquillamente lasciar perdere e tornarci sopra più tardi, più volte, con calma... non è che la ricorsione deve proprio essere il macigno che ti frena per giorni... Magari se passi oltre e aspetti di conoscere più algoritmi, di esserti fatto le ossa, di aver visto e fatto molti più ragionamenti... magari poi ti viene. Certo, non puoi evitarla per sempre... ma insomma non so proprio se mi ci incaponirei adesso.


Detto tutto questo, se vuoi provare un esercizio... laterale... guarda questo: https://pythoninwindows.blogspot.com/2019/01/esercizio-funzioni-ricorsive.html
In questo articolo spiego come si ragiona per risolvere un esercizio ricorsivo. Non è lo stesso che hai tu, ma appunto... Prova a lasciar perdere il tuo esercizio per un po', prova a seguire il ragionamento del mio articolo... troverai dei punti fermi che ti possono servire per tutti gli esercizi ricorsivi... poi magari riesci a riprendere in mano il tuo esercizio, e ti viene un po' più facile.

Ma ripeto, non è che casca il mondo, se rimandi il problema un po'.

davvero grazie per il consiglio e il sottinteso incoraggiamento. faro come dici tu. a presto