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!
-
5O 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?– Jefferson QuesadoCommented 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– L. LinharesCommented 4/04/2019 às 1:34
1 Resposta
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:
pow()
, de fato, não é seguro para calcular uma potência inteira, foi, portanto, substituído;while
por um for
, por concordar que era o mais adequado;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';
}
-
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 é sim2^n
. Inclusive, quando se tem um conjuntoA
, 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.– user142154Commented 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 essefor
disfarçado dewhile
), mas não vejo problemas no código além de ignorar o subconjunto vazio (que pode ser facilmente incluso fazendocombinacao = 0
no lugar decombinacao = 1
). Commented 5/04/2019 às 3:01 -
1Por 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 oprintf
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 -
1A 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