0

Olá gente preciso de ajuda com o seguinte algoritmo ele deve ter como entrada um vetor onde o usuário informa e o programa mostra as combinações possíveis, por ex: input = [1,2,3] output = [ [1,2,3], [1,2], [1,3], [2,3], [1], [2], [3], [] ] se alguém conseguir me ajudar vou agradecer muito!

2
  • 5
    O que foi tentado? Qual foi sua dificuldade? O que você não entendeu do problema de pegar o conjunto de todos os subconjuntos de outro conjunto? Commented 4/04/2019 às 1:02
  • o que eu fiz foi fazer a parte de ler o vetor com n numeros que o usuario informa, minha dificuldade é em montar os subconjuntos para casos genericos Commented 4/04/2019 às 1:34

1 Resposta 1

1

Intuitivamente é possível perceber que o número de combinações possíveis é igual a 2^n - 1 onde n é o número de elementos do vetor, assim, se o vetor possui um elemento o número de combinações é igual a 1, se possui 2, o número de combinações é igual a 3 e assim vai.

Se o número de combinações é igual a 2^n - 1 é possível representá-lo com os bits que compõem um int. Exemplo, se o vetor contém dois números, cada combinação pode ser representada do seguinte modo:

[1][2] corresponde a 11, pois ambos os números aparecem.

[1] corresponde a 10, pois apenas o primeiro número aparece.

[2] corresponde a 01, pois apenas o segundo número aparece.

Então, vamos à implementação do algoritmo. No código, eu usei a condição buffer_int % 2 == 0 para verificar se o bit na posição i é igual a 1 ou igual a 0. E usei a instrução buffer_int /= 2; para passar para o próximo bit. Confira-se:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdint.h>

int main(){

   int quantidade = 0;
   int numeros[31];
   /*31, pois (2^31 - 1) é o número máximo de combinações permitidade pelo programa.
   Seria relativamente fácil aumentar o número de combinações máxima para 2^63 - 1, 
   mas como o algoritmo tem complexidade exponencial, valores dessa grandeza não 
   são úteis do ponto de vista prático.*/  

   char buffer_str[64];

   //recebe os dados do usuario e cria o array
   while(quantidade < 31){
      printf("Entre um numero ou 'exit' para sair.\n");
      scanf("%s", &buffer_str);

      if(strcmp(buffer_str, "exit") == 0){
         break;
      }
      numeros[quantidade] = atoi(buffer_str);
      quantidade++;
   }

   int i;

   int32_t combinacao = 1;
   int buffer_int;

   while(combinacao < (int32_t) pow(2, quantidade)){

      buffer_int = combinacao;

      for(i = 0; i < quantidade; i++){
         //se o bit na posicao i é igual a 1 imprima o número
         if(buffer_int % 2 == 1){
            printf("%d ", numeros[i]);
         }
         //divide buffer_int por 2 para verificar o próximo bit
         buffer_int /= 2;
      }
      puts("");
      combinacao++;
   }
}

EDIT: gostei das sugestões realizadas nos comentários e fiz as seguintes alterações no código:

  • acrescentei o conjunto vazio ao conjunto de combinações possíveis;
  • pow(), de fato, não é seguro para calcular uma potência inteira, foi, portanto, substituído;
  • substitui o while por um for, por concordar que era o mais adequado;
  • utilizei a função sprintf() e as variáveis elemento_str e conjunto_str para diminuir a I/O excessiva e melhorar a perfomance;
  • E, por fim, também corrigi um bug que acontecia quanto o usuário inseria o número máximo de elementos (31). Não vou entrar em detalhes, mas o correto era usar o tipo uint32_t e não o tipo int32_t.

    Abaixo o trecho do código alterado:

     int i;
    
       uint32_t num_comb = 1;
       //num_comb == numero de combinações possíveis
       for(int i = 0; i < quantidade; i++){num_comb *= 2;}
       uint32_t combinacao;
       uint32_t buffer_int;
    
       char elemento_str[8];
       //"[] é o primeiro conjunto a ser impresso (conjunto vazio)."
       char conjunto_str[128] = "[]";
    
       for(combinacao = 0; combinacao < num_comb; combinacao++){
          buffer_int = combinacao;
    
          for(i = 0; i < quantidade; i++){
             //se o bit na posicao i é igual a 1 imprima o número
             if(buffer_int % 2 == 1){
                sprintf(elemento_str, "%d ", numeros[i]);
                strcat(conjunto_str, elemento_str);
             }
             //divide buffer_int por 2 para verificar o próximo bit
             buffer_int /= 2;
          }
         printf("%s\n", conjunto_str);
         conjunto_str[0] = '\0';
       }
    
    
    6
    • Só um detalhe: o subconjunto trivial vazio também está no resultado esperado, e vazio sempre é possível de ser obtido. Então, o número de subconjuntos possíveis de se formar com n elementos é sim 2^n. Inclusive, quando se tem um conjunto A, a operação matemática usada para indicar o conjunto de todos os subconjuntos é 2^A. Pude ver isso quando, ao listar as opções de subconjuntos para 2 elementos, você não citou a escolha 00, apenas as 11, 10, 01. De resto, sua base matemática pareceu adequadamente sólida, só terminando de ler a parte do código. Commented 5/04/2019 às 2:51
    • @JeffersonQuesado, você tem razão. Eu tomei como pressuposto que o conjunto vazio não estava incluído e fiz o código nesse sentido. Eu estou verificando também outra parte do código, no começo, eu testei até com algo em torno de 20 números, mais do que isso, estava demorando mais de um minuto para calcular. Mas depois que eu coloquei 31 digitos, houve um problema e eu estou verificando isso. Talvez algo esteja out of range. Depois, eu edito tudo.
      – user142154
      Commented 5/04/2019 às 2:58
    • Não compactuamos com alguns detalhes na implementação (eu jamais escreveria pow(2, quantidade) para uma potenciação inteira, por exemplo; nem tampouco faria nada de UI, apenas algoritmo e transferência de resultados para poder ser útil em outro ponto de código; nem esse for disfarçado de while), mas não vejo problemas no código além de ignorar o subconjunto vazio (que pode ser facilmente incluso fazendo combinacao = 0 no lugar de combinacao = 1). Commented 5/04/2019 às 3:01
    • 1
      Por coincidência, acabei de receber um voto positivo nesta resposta. Em algum momento lá eu falo para evitar I/O excessiva para problemas de computação competitiva. Pode ser algo proveitoso para você melhorar a performance do seu teste. Tem uma função chamada sprintf que escreve em uma string o que o printf escreve em um terminal. Tudo 100% memória, sem I/O. Vai deixar o código mais difícil de ler, mas melhoraria a performance. Commented 5/04/2019 às 3:11
    • 1
      A propósito, achei a fórmula para encontrar quantas vezes você vai imprimir. Apenas troque o 20 pelo número que será usado; no caso do 20, aproximadamente 10,5 milhões de escritas serão chamadas. Vide fórmula Commented 5/04/2019 às 3:35

    Você deve fazer log-in para responder a esta pergunta.

    Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .