programa en C ++ para imprimir todas las posibles subconjunto de un conjunto

En este programa en C ++, aprendemos cómo encontrar y imprimir la posible subconjunto de un conjunto ? Esta página no tiene lógica, el programa y la explicación a subconjuntos de un conjunto de impresión .

Planteamiento del problema:

Imprimir posible subconjunto de un conjunto

Ejemplo:

    input : {1,2,3,4}
output :
{}
{1}
{2}
{1,2}
{3}
{1,3}
{2,3}
{1,2,3}
{4}
{1,4}
{2,4}
{1,2,4}
{3,4}
{1,3,4}
{2,3,4}
{1,2,3,4}

Explicación:

El número total de posibles subconjunto de un conjunto puede tener es 2 ^ n , donde n es el número de elementos en el conjunto.

Podemos generar todo subconjunto posible utilizando contador binario.

class ejemplo:

considerar un conjunto ‘A’ que tiene elementos de {a, b, c} . Así que vamos a generar número binario hasta 2 ^ n – 1 (como vamos a 0 For también).

  • Aquí n es 3 lo que vamos a generar número binario hasta 2 ^ 3 – 1 (es decir 8-1 = 7)
  • después comprobaremos que mordió en contador binario está conectado o desconectado.
  • Si ITH bit está establecido, class ITH elemento del conjunto en el subconjunto actual.
  • Si ITH bits no está definida, excluir ITH elemento del conjunto en el subconjunto actual.

contador binario
subconjunto formado
Explicación

_16 3_

000 {} como todos los bits son unset, por lo excluir toda
001 {a} tan sólo se establece primero poco, vamos a include solamente primero elemento del conjunto es decir, ‘a’
010 {b} ya que sólo segundo bit se establece, vamos a class solamente segundo elemento del conjunto es decir, ‘b’
011 {a, b} como se establecen 1ª y 2ª bits de, vamos a class primero y segundo elemento del conjunto es decir, ‘a’ y ‘b’
100 {c} como se establece sólo tercera bit, vamos a class tercera elemento del conjunto es decir, ‘c’
101 {a, c} como se establecen 1º y 3º los ​​bits, vamos a include primero y tercero elemento de la ‘c’
110 conjunto es decir, ‘a’ y {b, c} como se establecen 2ª y 3ª bits de, vamos a class segundo y tercero elemento del conjunto es decir, ‘b’ y ‘c’
111 ​​ {a , b, c} todos los bits se establecen, class todos los elementos del conjunto.

Programa:

#include <bits/stdc++.h>
using namespace std;
void allPossibleSubset(int arr[], int n)
{
int count = pow(2, n);
// The outer for loop will run 2^n times to print all subset .
// Here variable i will act as a binary counter
for (int i = 0; i < count; i++) {
// The inner for loop will run n times ,
// As the maximum number of elements a set can have is n
// This loop will generate a subset
for (int j = 0; j < n; j++) {
// This if condition will check if jth bit in
// binary representation of i is set or not
// if the value of (i & (1 << j)) is not 0 ,
// include arr[j] in the current subset
// otherwise exclude arr[j]
if ((i & (1 << j)) != 0)
cout << arr[j] << " ";
}
cout << "n";
}
}
int main()
{
int n;
cout << "Enter size of the setn";
cin >> n;
int arr[n];
cout << "Enter Elements of the setn";
for (int i = 0; i < n; i++)
cin >> arr[i];
allPossibleSubset(arr, n);
return 0;
}

salida

Enter size of the set
4
Enter Elements of the set
1 2 3 4
1
2
1 2
3
1 3
2 3
1 2 3
4
1 4
2 4
1 2 4
3 4
1 3 4
2 3 4
1 2 3 4


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *