terça-feira, 4 de dezembro de 2012

Gerando todos os subconjuntos


Para resolver alguns tipos de problemas, precisamos construir de um algoritmo para gerar todos os subconjuntos para encontrar subconjunto em particular que satisfaz uma dada propriedade.

O algoritmo para construir todos os subconjuntos pode ser usado em algoritmo de busca  exaustiva que consiste em enumerar explicitamente todas os subconjuntos e testá-los   e/ou em um algoritmo de enumeração implícita.

Algoritmo para gerar todos os subconjuntos
#include <stdio.h>
#include <stdlib.h>
int conj[32];
int cont;
void subconjunto(int i, int n){
 int j;
 if(i>n){
  printf("%d subconjunto:",++cont);
  for(j=1;j<=n;j++)
   if(conj[j]==1)
    printf("%d ",j);
  printf("\n");
 }else{
  conj[i] = 1;
  subconjunto(i+1,n);
  conj[i] = 0;
  subconjunto(i+1,n);
 }
}

int main(){
 int n;
 scanf("%d",&n);
 cont = 0;
 subconjunto(1,n);
 return 0;
}














Saída

3
1 subconjunto:1 2 3
2 subconjunto:1 2
3 subconjunto:1 3
4 subconjunto:1
5 subconjunto:2 3
6 subconjunto:2
7 subconjunto:3
8 subconjunto:



Tabela da execução do algoritmo
Gerando todos os subconjunto usando bitsmask
Algoritmo para gerar todos os subconjuntos
#include <stdio.h>
#include <stdlib.h>

int main(){
 int n,i,j;
 scanf("%d",&n);
 
 for(i=0;i<(1<<n);i++){
  printf("subconjunto %d: ",i);
  for(j=0;j<n;j++){
   if((i & (1<<j))!= 0){
    printf("%d ",j+1);
   }
  }
  printf("\n");
 }
 return 0;
}

Saída

3
subconjunto 0:
subconjunto 1: 1
subconjunto 2: 2
subconjunto 3: 1 2
subconjunto 4: 3
subconjunto 5: 1 3
subconjunto 6: 2 3
subconjunto 7: 1 2 3






2 comentários:

Itamar disse...

pq no primeiro algoritmo vc começa o for de 1?

Wladimir Araújo Tavares disse...

Erro meu!