Newsgroup: it.comp.lang.pascal
Titolo: Generare tutti i possibili sottoinsiemi di un dato insieme

Ciao a tutti,
il problema che mi hanno assegnato e' quello di realizzare una funzione
ricorsiva che generi tutti i sottoinsiemi di un dato insieme, ovvero
P(S). Se S e' un insieme S={a,b,c}
P(S)={0,{a},{b},{c},{a,b},{a,c},{b,c},S} . Nel mio caso l'insiemi sono
rappresentati da liste. 
Io avevo pensato di risolvere il problema basandomi sulla cardinalita'
dell'insieme.
Grazie a tutti per eventuali suggerimenti.
Alex

...


devo sempre fare le combinazioni a coppia oppure {a,b,c},{c,d,e} ad esempio
[vedi sopra]
P({a,b,c,d,e}) = { {}, {a}, {b}, {c}, {d}, {e}, {a,b}, {a,c}, {a,d},
{a,e}, {b,c}, {b,d}, {b,e}, {c,d}, {c,e}, {d,e}, {a,b,c}, {a,b,d},
{a,b,e}, {a,c,d}, {a,c,e}, {a,d,e}, {b,c,d}, {b,c,e}, {b,d,e},
{c,d,e}, {a,b,c,d}, {a,b,c,e}, {a,b,d,e}, {a,c,d,e}, {b,c,d,e},
{a,b,c,d,e} }
Spero di non aver sbagliato il calcolo delle parti, perche' il
programma che sto costruendo si basa proprio su questo procedimento
ricorsivo ! ;)

dell'insieme.
Io l'ho risolto nel modo seguente in cui la funzione "cuore" del
programma e' "combina()"  :
program Calcola_Parti ;
type lista_p   = ^tag_lista ;
     tag_lista = record
                   c : char ;
                   prossimo : lista_p ;
                 end ;
     parte_p      = ^tag_parte ;
     tag_parte    = record
                      lista : lista_p ;
                      prossimo : parte_p ;
                    end ;
procedure inserisci_in_lista (var p : lista_p ; c : char ) ;
begin
  if ( p = NIL ) then
  begin
    new ( p ) ;
    p^.c := c ;
    p^.prossimo := NIL ;
  end
  else inserisci_in_lista ( p^.prossimo, c ) ;
end ;
procedure rimuovi_ultimo_da_lista ( var p : lista_p ) ;
begin
  if ( p^.prossimo = NIL ) then
  begin
     dispose ( p ) ;
     p := NIL ;
  end
  else rimuovi_ultimo_da_lista ( p^.prossimo ) ;
end ;
procedure scrivi_lista ( p : lista_p ) ;
begin
  if ( p <> NIL ) then
  begin
    write (p^.c,'->') ;
    scrivi_lista ( p^.prossimo ) ;
  end else writeln ( 'NIL' ) ;
end ;
procedure scrivi_parti ( p : parte_p ) ;
begin
  if ( p <> NIL ) then
  begin
     scrivi_lista ( p^.lista ) ;
     scrivi_parti ( p^.prossimo ) ;
  end else writeln ( 'NIL' ) ;
end ;
procedure copia_lista ( var dest_p : lista_p ;
                            source_p : lista_p ) ;
begin
  if ( source_p = NIL ) then dest_p := NIL
  else
  begin
    new ( dest_p ) ;
    dest_p^.c := source_p^.c ;
    copia_lista ( dest_p^.prossimo, source_p^.prossimo ) ;
  end ;
end ;
procedure salva_sottoinsieme ( L : lista_p ; var P : parte_p )  ;
begin
  if ( P = NIL ) then
  begin
    new ( P ) ;
    P^.prossimo := NIL ;
    copia_lista ( P^.lista, L ) ;
  end
  else salva_sottoinsieme ( L, P^.prossimo ) ;
end ;
procedure combina ( L : lista_p ;
                    var Lista : lista_p ;
                    var P : parte_p ) ;
begin
  while ( L <> NIL ) do
  begin
    inserisci_in_lista ( Lista, L^.c ) ;
    salva_sottoinsieme ( Lista, P ) ;
    combina ( L^.prossimo, Lista, P ) ;
    rimuovi_ultimo_da_lista ( Lista ) ;
    L := L^.prossimo ;
  end ;
end ;
{ *** main program *** }
var L, K : lista_p ;
    P : parte_p ;
begin
  L := NIL ;
  K := NIL ;
  P := NIL ;
  writeln ( 'calcolo delle parti di un insieme' ) ;
  inserisci_in_lista ( L, 'A' ) ;
  inserisci_in_lista ( L, 'B' ) ;
  inserisci_in_lista ( L, 'C' ) ;
  inserisci_in_lista ( L, 'D' ) ;
  combina ( L, K, P ) ;
  scrivi_parti ( P ) ;
end.
L'output prodotto e' il seguente :
calcolo delle parti di un insieme
A->NIL
A->B->NIL
A->B->C->NIL
A->B->C->D->NIL
A->B->D->NIL
A->C->NIL
A->C->D->NIL
A->D->NIL
B->NIL
B->C->NIL
B->C->D->NIL
B->D->NIL
C->NIL
C->D->NIL
D->NIL
NIL
che, come puoi vedere e' corretto...