algoritmo creazione sottoinsiemi

[Oceans11]

ciao raga!
vado subito al dunque..


...ho un vettore che rappresenta un insieme di numeri naturali e devo scrivere su file i vari sottoinsiemi dell'insieme di partenza!!!
esempio:

l'insieme {1,2,3,4} ha 2^n (n=4) sottoinsieme e precisamente:


- l'insieme vuoto!
- 1
- 2
- 3
- 4
- 1,2
- 1,3
- 1,4
- 2,3
- 2,4
- 3,4
- 1,2,3
- 1,3,4
- 1,2,4
- 2,3,4
- 1,2,3,4


ho problemi solo con l'algoritmo di creazione dei sottoinsiemi per il resto (memorizzazione degli n elementi e stampa su file è tutto ok!!!)
se qualcuno di voi a suggerimenti da darmi è proprio un santo!!!
grazie!

[/\/\@®¢Ø]

Non hai specificato in che linguaggio ti interessa, per cui ti daro' l'algoritmo in python :p.

E' abbastanza semplice se lo pensi in modo ricorsivo, partendo dal caso piu' semplice e aggiungendo man mano elementi.
I sottoinsiemi dell'insieme vuoto e' dato dall'insieme contenente solo l'insieme vuoto.
A questo punto, se abbiamo i sottoinsiemi P(X) di un insieme X, i sottoinsiemi di X u {x} sono dati da P(X) u { {x} u Y | Y in P(X) }, ovvero utti i sottoinsiemi di X piu' tutti i sottoinsiemi di X a cui abbiamo aggiunto il nuovo elemento.

La "traduzione" in algoritmo e' immediata (te la faccio in python per semplicita'):

def subsets(x):
if x == []:
return [[]]
else:
subs = subsets(x[1:])
return subs + [ [x[0]] + xs for xs in subs ]

[anx721]

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


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 già 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.

[hakermatik]

Non hai specificato in che linguaggio ti interessa, per cui ti daro' l'algoritmo in python :p.

E' abbastanza semplice se lo pensi in modo ricorsivo, partendo dal caso piu' semplice e aggiungendo man mano elementi.
I sottoinsiemi dell'insieme vuoto e' dato dall'insieme contenente solo l'insieme vuoto.
A questo punto, se abbiamo i sottoinsiemi P(X) di un insieme X, i sottoinsiemi di X u {x} sono dati da P(X) u { {x} u Y | Y in P(X) }, ovvero utti i sottoinsiemi di X piu' tutti i sottoinsiemi di X a cui abbiamo aggiunto il nuovo elemento.

La "traduzione" in algoritmo e' immediata (te la faccio in python per semplicita'):

def subsets(x):
if x == []:
return [[]]
else:
subs = subsets(x[1:])
return subs + [ [x[0]] + xs for xs in subs ]


scrivo per conto di oceans11.... potreste postarmi il codice in C.... thanks

[hakermatik]

up!!

[Oceans11]

sì il programma lo devo scrivere in c...
...non l'ho detto subito solo perchè mi sarei accontentato anche solo di una spiegazione...mmm....'in italiano'!!


cmq perdonate la mia ignoranza ma proprio non riesco a capire la spiegazione ricorsiva di /\/\@®¢Ø!

apparte il passo base non ho capito poi + di tanto!

[anx721]

Ti riscrivo il mio in modo piu attinente al tuo esercizio:

Sia v il vettore di n numeri interi che rappresenta l'insieme, si un vettore di n interi inizializzato a zero, e file il puntatore al file in cui vuoi scrivere:


#include <stdio.h>
#include <stdlib.h>


void generaSosttoInsiemi(FILE *file,int v[], int si[], int k, int n){
int i= 0;
if(k == n - 1){
for(i = 0; i < n; i++){
if(si[i] == 1){
printf("%d ", v[i]);
fprintf(file, "%d ", v[i]);
}
}
printf("\n");
fprintf(file, "\n");
}
else
for(i = 0; i <= 1; i++){
si[k + 1] = i;
generaSosttoInsiemi(file, v, si, k + 1, n);
}
}

int main(){
FILE *file = fopen("insiemi.txt", "w");
int v[] = {0, 1, 2, 3, 4, 5, 6, 7};
int si[] = {0, 0, 0, 0, 0, 0, 0, 0};
//generaSosttoInsiemi va chiamata passandole il file, i vettorI
//v e si, -1 e la dimensione n del vettore
generaSosttoInsiemi(file, v, si, -1, 8);
fclose(file);
return 0;
}

[K@IN]

SENTI IL PROGRAMMA IN C CON LA CREAZIONE DEI SOTTOINSIEMI FUNZIONA E TI RINGRAZIO ... ORA PERO' POTRESTI SPIEGARCI "MOLTO SEMPLICEMENTE" COME FUNZIONA.... E' PER UN ESAME ORALE :(

[anx721]

è la traduzione dell'algoritmo che ti ho messo sopra e ti ho anche messo il txt con il disegnino..parti da li per capirlo e semmai fai domande in base a quello che ti ho scritto nel primo post