Split sets

Question

Hello people need help with the following algorithm it must have as input an array where the user informs and the program shows the possible combinations, for example: input = [1,2,3] output = [ [1,2,3], [1,2], [1,3], [2,3], [1], [2], [3], [] ] If anyone can help me I’ll thank you very much!

Answer 1

Intuitively it is possible to realize that the number of possible combinations is equal to 2 n - 1 where n is the number of elements of the vector, so if the vector has an element the number of combinations is 1, if it has 2, the number of combinations is 3 and so on.

If the number of combinations is equal to 2 n - 1 it is possible to represent it with the bits that make up a int. For example, if the vector contains two numbers, each combination can be represented as follows:

[1][2] corresponds to 11, as both numbers appear.

[1] corresponds to 10, because only the first number appears.

[2] corresponds to 01, because only the second number appears.

So, let’s go to the implementation of the algorithm. In the code, I used the condition buffer_int % 2 == 0 to check whether the bit in position i is equal to 1 or equal to 0. And I used the instruction buffer_int /= 2; to move to the next bit. Check yourself:

#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: I liked the suggestions made in the comments and made the following changes to the code:

I added the empty set to the set of possible combinations;

pow(), in fact, it is not safe to calculate an entire power, it has therefore been replaced;

replaces the while by a for, for agreeing that it was the most appropriate;

I used the function sprintf() and the variables elemento_str and conjunto_str to decrease excessive I/O and improve performance;

And finally, I also fixed a bug that happened when the user entered the maximum number of elements (31). I won’t go into details, but the right thing to do would be to use the guy uint32_t and not the kind int32_t.

Below the excerpt of the changed code:

 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';
   }