Cerco spiegazione algoritmo

[TommyGun]

Sapreste spiegarmi questo algoritmo in termini di passi effettuati dalla ricorsione, non riesco a comprendere come possa stampare(e lo fà!) tutti i sottoinsiemi di un insieme.

SOTTOINSIEMI(SOL,K,N)

[TommyGun]

scusate!!

SOTTOINSIEMI(SOL,K,N)
IF K=N THN STAMPA (SOL)
ELSE
FOR i=0 TO 1 DO
SOL[K+1]=i
SOTTOINSIEMI(SOL,K+1,N)
ENDFOR
END

Viene utilizzata la tecnica di programmazione Backtraking,
se c'è qualche esperto lo prego di aiutarmi!

Grazie mille.

[ale500]

magari così è più leggibile.

SOTTOINSIEMI(SOL,K,N) 
   IF K=N THEN
      STAMPA (SOL) 
   ELSE 
      FOR i=0 TO 1 DO 
         SOL[K+1]=i 
         SOTTOINSIEMI(SOL,K+1,N) 
      ENDFOR 
   END

ma magari ti avranno spiegato cosa sono i parametri SOL, K e N che passo alla "funzione" o mi sono perso già qualcosa?

[TommyGun]

Originariamente inviato da ale500
magari così è più leggibile.

SOTTOINSIEMI(SOL,K,N) 
   IF K=N THEN
      STAMPA (SOL) 
   ELSE 
      FOR i=0 TO 1 DO 
         SOL[K+1]=i 
         SOTTOINSIEMI(SOL,K+1,N) 
      ENDFOR 
   END

ma magari ti avranno spiegato cosa sono i parametri SOL, K e N che passo alla "funzione" o mi sono perso già qualcosa?

si si pian piano metto a posto tutti i tasselli
dunque Sol si può pensare come un vettore caratteristico di 0,1 formato da N elementi, in cui Sol[k]==1 sse l'elemento k -esimo fa parte del sottoinsieme che stò costruendo in Sol.
K è solo un indice per manipolare il vettore, e N rappresenta il nr di elementi dell'insieme.

faccio un esempio di 2 sottoinsiemi di un insieme formato da
N=3 elementi= {a,b,c}
1) {a} rappresentato dall'algo come Sol={1,0,0}
2) {a,c} // // Sol={1,0,1}

Meglio no!?!

[anx721]

Un insieme di N elementi ha 2^N (2 alla N) sottoinsiemi; difatti puoi mettere tali insiemi in corrispondenza biunivoca con l'insieme delle stringhe binarie di lunghezza N, proprio nel modo fatto dall'algoritmo che associa ogni generico sottoinsieme ad una generica sequenza di zeri ed uni, tale che sol[k] == 1 sse il k-esimo elemento appartiene al sottoinsieme.

Ora, per costruire un sottoinsieme quello che devi fare è passare in rassegna tutti gli eleemnti, e per ciascuno decidere se considerarlo o non considerarlo. In particolare, supponi di aver gàa considerato i primi k elementi, ora ti tocca decidere se prendere o meno il k+1-esimo elemento, cioè decidere se porre sol[k+1]=0 o sol[k+]=1; dopodichè continui col k+2-esimo elemento, ovvero ripeti la procedura incrementando k; quando k == N significa che hai preso una decisione su tutti gli elementi, e quindi puoi stampare il sottoinsieme.

Nel caso del tuo algoritmo non vuoi solo creare un generico sottoinsieme, ma li vuoi stampare tutti, quindi, quando consideri il generico elemento k, prima poni sol[k]=0, scartando cosi k dal sottoinsieme, e ciò ti permette di costruire tutti i sottoinsiemi che non hanno k; poi richiami la proceduira ricorsivamente anche con sol[k]=1, in modo da poter costruire tutti i sottoinsiemi che hanno k.

Costurire questi sottoinsiemi è come costruire tutte le stringhe binarie di lunghezza N che sono proprio 2^N, e difatti ogni chiamata ricorsiva si dirama in due sottochiamate, cosi alla fine si avranno 2^N chiamate ricorsive.

[ale500]

Originariamente inviato da TommyGun
e N rappresenta il nr di elementi dell'insieme.

faccio un esempio di 2 sottoinsiemi di un insieme formato da
N=3 elementi= {a,b,c}
1) {a} rappresentato dall'algo come Sol={1,0,1}
2) {a,c} // // Sol={1,0,2}

Meglio no!?!

scusa ma non dovrebbe essere così?
N rappresenta il numero di elementi dell'insieme e quindi parte d 1 e non da 0.

fammi sapere.

[TommyGun]

Ok ti ringrazio per la risposta dettagliatissima,
ma il mio quesito non era proprio questo,
nel senso, sò bene ciò che viene prodotto dall'algo,
ma non riesco a capire quali sono i passi effettuati dalla
ricorsione nella costruzione dei vari sottoinsiemi,
cioè come si comporta con una chiamata ricorsiva all'interno di un ciclo FOR.

Originariamente inviato da anx721
Un insieme di N elementi ha 2^N (2 alla N) sottoinsiemi; difatti puoi mettere tali insiemi in corrispondenza biunivoca con l'insieme delle stringhe binarie di lunghezza N, proprio nel modo fatto dall'algoritmo che associa ogni generico sottoinsieme ad una generica sequenza di zeri ed uni, tale che sol[k] == 1 sse il k-esimo elemento appartiene al sottoinsieme.

Ora, per costruire un sottoinsieme quello che devi fare è passare in rassegna tutti gli eleemnti, e per ciascuno decidere se considerarlo o non considerarlo. In particolare, supponi di aver gàa considerato i primi k elementi, ora ti tocca decidere se prendere o meno il k+1-esimo elemento, cioè decidere se porre sol[k+1]=0 o sol[k+]=1; dopodichè continui col k+2-esimo elemento, ovvero ripeti la procedura incrementando k; quando k == N significa che hai preso una decisione su tutti gli elementi, e quindi puoi stampare il sottoinsieme.

Nel caso del tuo algoritmo non vuoi solo creare un generico sottoinsieme, ma li vuoi stampare tutti, quindi, quando consideri il generico elemento k, prima poni sol[k]=0, scartando cosi k dal sottoinsieme, e ciò ti permette di costruire tutti i sottoinsiemi che non hanno k; poi richiami la proceduira ricorsivamente anche con sol[k]=1, in modo da poter costruire tutti i sottoinsiemi che hanno k.

Costurire questi sottoinsiemi è come costruire tutte le stringhe binarie di lunghezza N che sono proprio 2^N, e difatti ogni chiamata ricorsiva si dirama in due sottochiamate, cosi alla fine si avranno 2^N chiamate ricorsive.

[TommyGun]

Originariamente inviato da ale500
scusa ma non dovrebbe essere così?
N rappresenta il numero di elementi dell'insieme e quindi parte d 1 e non da 0.

fammi sapere.

Beh no, è più conveniente utilizzare un vettore caratteristico di 0,1 tanto il nr di elementi del sottoinsieme in costruzione non interessa.

Ciao.

[anx721]

Originariamente inviato da TommyGun
Ok ti ringrazio per la risposta dettagliatissima,
ma il mio quesito non era proprio questo,
nel senso, sò bene ciò che viene prodotto dall'algo,
ma non riesco a capire quali sono i passi effettuati dalla
ricorsione nella costruzione dei vari sottoinsiemi,
cioè come si comporta con una chiamata ricorsiva all'interno di un ciclo FOR.

per capirlo devi provare ad eseguire l'algoritmo con carta e penna, magari con N = 3; quando si ha una chiamata ricorsiva simula la chiamata sui nuovi argomenti su un nuovo foglio, quando la chiamata termina ritorna sul foglio da cui sei partito, il tutto per simulare lo stack di chiamate che si ha per effetto delle chiamate ricorsive.

[anx721]

Ti riporto uno schema che dovrebe chiarirti come si susseguono le chiamate ricorsive; ogni chiamata si dirama in due sottochiamate, la prima imposta il corrente indice k a 0 e l'altra imposta il corrente indice k a 1; l'ordine con cui sono eseguite le chiamate è quello mostrato dalle lettere sugli archi dell'albero; SI = Sottoinsiemi

                                       
                                       _____D_____SI([000],3,3)
                                      |
                                      |
                      ______C____SI([000],2,3)
                     |                |  
                     |                |______E______SI([001],3,3)
                     |                
        ___B___SI([000],1,3)            _____G______SI([010],3,3)
       |             |                 |
       |             |                 |          
       |             |_____F_____ SI([010],2,3)  
       |                               |        
       |                               |_____H_______SI([011],3,3)
       |                               
       |                                           
       |
A SI([000],0,3)                         
       |                               ______M_______SI([100],3,3)
       |                              |
       |                              |            
       |              _____L_____SI([100],2,3)                 
       |             |                |     
       |             |                |______N_______SI([101],3,3)
       |             |
       |___I____SI([100],1,3)          ______P______SI([110],3,3)
                     |                |        
                     |                |           
                     |____O_____SI([110],2,3)
                                      |
                                      |______Q______SI([111],3,3)