Set de poder

Conjunto potencia: El conjunto potencia P(S) de un conjunto S es el conjunto de todos los subconjuntos de S . Por ejemplo S = {a, b, c} entonces P(s) = {{}, {a}, {b}, {c}, {a,b}, {a, c}, {b, c} , {a B C}}.
Si S tiene n elementos, entonces P(s) tendrá 2 n elementos

Ejemplo: 

Set = [a,b,c]
power_set_size = pow(2, 3) = 8
Ejecutar para contador binario = 000 a 111

Valor del subconjunto de contadores
   000 -> Conjunto vacío
   001 -> a
   010 -> b
   011 -> ab
   100 -> c
   101 -> ac
   110 -> bc
   111 -> abc

Algoritmo: 

Entrada: Set[], set_size
1. Obtener el tamaño de potencia set
      powet_set_size = pow(2, set_size)
2 Bucle para el contador de 0 a pow_set_size
    (a) Bucle para i = 0 a set_size
         (i) Si i-ésimo bit en el contador es conjunto
                Imprime el elemento i-ésimo del conjunto para este subconjunto
   (b) Imprime el separador para los subconjuntos, es decir, nueva línea

Método 1:
Para un conjunto[] S dado, el conjunto potencia se puede encontrar generando todos los números binarios entre 0 y 2 n -1 , donde n es el tamaño del conjunto. 
Por ejemplo, para el conjunto S { x , y , z } , genere todos los números binarios de 0 a 2 3 -1 y para cada número generado, el conjunto correspondiente se puede encontrar considerando los bits establecidos en el número.

A continuación se muestra la implementación del enfoque anterior.

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print all the power set
void printPowerSet(char* set, int set_size)
{
    // Set_size of power set of a set with set_size
    // n is (2^n-1)
    unsigned int pow_set_size = pow(2, set_size);
    int counter, j;
 
    // Run from counter 000..0 to 111..1
    for (counter = 0; counter < pow_set_size; counter++) {
        for (j = 0; j < set_size; j++) {
            // Check if jth bit in the counter is set
            // If set then print jth element from set
            if (counter & (1 << j))
                cout << set[j];
        }
        cout << endl;
    }
}
 
/*Driver code*/
int main()
{
    char set[] = { 'a', 'b', 'c' };
    printPowerSet(set, 3);
    return 0;
}
 
// This code is contributed by SoM15242

C

#include <stdio.h>
#include <math.h>
 
void printPowerSet(char *set, int set_size)
{
    /*set_size of power set of a set with set_size
      n is (2**n -1)*/
    unsigned int pow_set_size = pow(2, set_size);
    int counter, j;
 
    /*Run from counter 000..0 to 111..1*/
    for(counter = 0; counter < pow_set_size; counter++)
    {
      for(j = 0; j < set_size; j++)
       {
          /* Check if jth bit in the counter is set
             If set then print jth element from set */
          if(counter & (1<<j))
            printf("%c", set[j]);
       }
       printf("\n");
    }
}
 
/*Driver program to test printPowerSet*/
int main()
{
    char set[] = {'a','b','c'};
    printPowerSet(set, 3);
    return 0;
}

Java

// Java program for power set
import java .io.*;
 
public class GFG {
     
    static void printPowerSet(char []set,
                            int set_size)
    {
         
        /*set_size of power set of a set
        with set_size n is (2**n -1)*/
        long pow_set_size =
            (long)Math.pow(2, set_size);
        int counter, j;
     
        /*Run from counter 000..0 to
        111..1*/
        for(counter = 0; counter <
                pow_set_size; counter++)
        {
            for(j = 0; j < set_size; j++)
            {
                /* Check if jth bit in the
                counter is set If set then
                print jth element from set */
                if((counter & (1 << j)) > 0)
                    System.out.print(set[j]);
            }
             
            System.out.println();
        }
    }
     
    // Driver program to test printPowerSet
    public static void main (String[] args)
    {
        char []set = {'a', 'b', 'c'};
        printPowerSet(set, 3);
    }
}
 
// This code is contributed by anuj_67.

Python3

# python3 program for power set
 
import math;
 
def printPowerSet(set,set_size):
     
    # set_size of power set of a set
    # with set_size n is (2**n -1)
    pow_set_size = (int) (math.pow(2, set_size));
    counter = 0;
    j = 0;
     
    # Run from counter 000..0 to 111..1
    for counter in range(0, pow_set_size):
        for j in range(0, set_size):
             
            # Check if jth bit in the
            # counter is set If set then
            # print jth element from set
            if((counter & (1 << j)) > 0):
                print(set[j], end = "");
        print("");
 
# Driver program to test printPowerSet
set = ['a', 'b', 'c'];
printPowerSet(set, 3);
 
# This code is contributed by mits.

C#

// C# program for power set
using System;
 
class GFG {
     
    static void printPowerSet(char []set,
                            int set_size)
    {
        /*set_size of power set of a set
        with set_size n is (2**n -1)*/
        uint pow_set_size =
              (uint)Math.Pow(2, set_size);
        int counter, j;
     
        /*Run from counter 000..0 to
        111..1*/
        for(counter = 0; counter <
                   pow_set_size; counter++)
        {
            for(j = 0; j < set_size; j++)
            {
                /* Check if jth bit in the
                counter is set If set then
                print jth element from set */
                if((counter & (1 << j)) > 0)
                    Console.Write(set[j]);
            }
             
            Console.WriteLine();
        }
    }
     
    // Driver program to test printPowerSet
    public static void Main ()
    {
        char []set = {'a', 'b', 'c'};
        printPowerSet(set, 3);
    }
}
 
// This code is contributed by anuj_67.

PHP

<?php
// PHP program for power set
 
function printPowerSet($set, $set_size)
{
 
    // set_size of power set of
    // a set with set_size
    // n is (2**n -1)
    $pow_set_size = pow(2, $set_size);
    $counter; $j;
 
    // Run from counter 000..0 to
    // 111..1
    for($counter = 0; $counter < $pow_set_size;
                                    $counter++)
    {
        for($j = 0; $j < $set_size; $j++)
        {
             
            /* Check if jth bit in
               the counter is set
               If set then print
               jth element from set */
            if($counter & (1 << $j))
                echo $set[$j];
        }
         
    echo "\n";
    }
}
 
    // Driver Code
    $set = array('a','b','c');
    printPowerSet($set, 3);
 
// This code is contributed by Vishal Tripathi
?>

Javascript

<script>
// javascript program for power setpublic
 
    function printPowerSet(set, set_size)
    {
 
        /*
         * set_size of power set of a set with set_size n is (2**n -1)
         */
        var pow_set_size = parseInt(Math.pow(2, set_size));
        var counter, j;
 
        /*
         * Run from counter 000..0 to 111..1
         */
        for (counter = 0; counter < pow_set_size; counter++)
        {
            for (j = 0; j < set_size; j++)
            {
             
                /*
                 * Check if jth bit in the counter is set If set then print jth element from set
                 */
                if ((counter & (1 << j)) > 0)
                    document.write(set[j]);
            }
            document.write("<br/>");
        }
    }
 
    // Driver program to test printPowerSet
        let set = [ 'a', 'b', 'c' ];
        printPowerSet(set, 3);
 
// This code is contributed by shikhasingrajput
</script>
Producción

a
b
ab
c
ac
bc
abc

Complejidad de Tiempo: O(n2 n )
Espacio Auxiliar: O(1)

Método 2: (ordenado por cardinalidad)

En la array auxiliar de bool, establezca todos los elementos en 0. Eso representa un conjunto vacío. Establezca el primer elemento de la array auxiliar en 1 y genere todas las permutaciones para producir todos los subconjuntos con un elemento. Luego establezca el segundo elemento en 1, lo que producirá todos los subconjuntos con dos elementos, repita hasta que se incluyan todos los elementos.

A continuación se muestra la implementación del enfoque anterior.

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print all the power set
void printPowerSet(char set[], int n)
{
    bool *contain = new bool[n]{0};
     
    // Empty subset
    cout << "" << endl;
    for(int i = 0; i < n; i++)
    {
        contain[i] = 1;
        // All permutation
        do
        {
            for(int j = 0; j < n; j++)
                if(contain[j])
                    cout << set[j];
            cout << endl;
        } while(prev_permutation(contain, contain + n));
    }
}
 
/*Driver code*/
int main()
{
    char set[] = {'a','b','c'};
    printPowerSet(set, 3);
    return 0;
}
 
// This code is contributed by zlatkodamijanic

Python3

# Python3 program for the above approach
 
# A function which gives previous
# permutation of the array
# and returns true if a permutation
# exists.
def prev_permutation(str):
 
    # Find index of the last
    # element of the string
    n = len(str) - 1
 
    # Find largest index i such
    # that str[i - 1] > str[i]
    i = n
    while (i > 0 and str[i - 1] <= str[i]):
        i -= 1
 
    # If string is sorted in
    # ascending order we're
    # at the last permutation
    if (i <= 0):
        return False
 
    # Note - str[i..n] is sorted
    # in ascending order Find
    # rightmost element's index
    # that is less than str[i - 1]
    j = i - 1
    while (j + 1 <= n and str[j + 1] < str[i - 1]):
        j += 1
 
    # Swap character at i-1 with j
    temper = str[i - 1]
    str[i - 1] = str[j]
    str[j] = temper
 
    # Reverse the substring [i..n]
    size = n-i+1
    for idx in range(int(size / 2)):
        temp = str[idx + i]
        str[idx + i] = str[n - idx]
        str[n - idx] = temp
 
    return True
 
# Function to print all the power set
def printPowerSet(set, n):
 
    contain = [0 for _ in range(n)]
 
    # Empty subset
    print()
 
    for i in range(n):
        contain[i] = 1
 
        # To avoid changing original 'contain'
        # array creating a copy of it i.e.
        # "Contain"
        Contain = contain.copy()
 
        # All permutation
        while True:
            for j in range(n):
                if (Contain[j]):
                    print(set[j], end="")
            print()
            if not prev_permutation(Contain):
                break
 
# Driver code
set = ['a', 'b', 'c']
printPowerSet(set, 3)
 
# This code is contributed by phasing17

C#

// C# program for the above approach
 
using System;
using System.Linq;
using System.Collections.Generic;
 
class GFG
{
 
  // A function which gives previous
  // permutation of the array
  // and returns true if a permutation
  // exists.
  static bool prev_permutation(int[] str)
  {
    // Find index of the last
    // element of the string
    int n = str.Length - 1;
 
    // Find largest index i such
    // that str[i - 1] > str[i]
    int i = n;
    while (i > 0 && str[i - 1] <= str[i]) {
      i--;
    }
 
    // If string is sorted in
    // ascending order we're
    // at the last permutation
    if (i <= 0) {
      return false;
    }
 
    // Note - str[i..n] is sorted
    // in ascending order Find
    // rightmost element's index
    // that is less than str[i - 1]
    int j = i - 1;
    while (j + 1 <= n && str[j + 1] < str[i - 1]) {
      j++;
    }
 
    // Swap character at i-1 with j
    var temper = str[i - 1];
    str[i - 1] = str[j];
    str[j] = temper;
 
    // Reverse the substring [i..n]
    int size = n - i + 1;
    Array.Reverse(str, i, size);
 
    return true;
  }
 
  // Function to print all the power set
  static void printPowerSet(char[] set, int n)
  {
 
    int[] contain = new int[n];
    for (int i = 0; i < n; i++)
      contain[i] = 0;
 
    // Empty subset
    Console.WriteLine();
    for (int i = 0; i < n; i++) {
      contain[i] = 1;
 
      // To avoid changing original 'contain'
      // array creating a copy of it i.e.
      // "Contain"
      int[] Contain = new int[n];
      for (int indx = 0; indx < n; indx++) {
        Contain[indx] = contain[indx];
      }
 
      // All permutation
      do {
        for (int j = 0; j < n; j++) {
          if (Contain[j] != 0) {
            Console.Write(set[j]);
          }
        }
        Console.Write("\n");
 
      } while (prev_permutation(Contain));
    }
  }
 
  /*Driver code*/
  public static void Main(string[] args)
  {
    char[] set = { 'a', 'b', 'c' };
    printPowerSet(set, 3);
  }
}
 
// This code is contributed by phasing17

Javascript

// JavaScript program for the above approach
 
// A function which gives previous
// permutation of the array
// and returns true if a permutation
// exists.
function prev_permutation(str){   
    // Find index of the last
    // element of the string
    let n = str.length - 1;
  
    // Find largest index i such
    // that str[i - 1] > str[i]
    let i = n;
    while (i > 0 && str[i - 1] <= str[i]){
        i--;
    }  
       
    // If string is sorted in
    // ascending order we're
    // at the last permutation
    if (i <= 0){
        return false;
    }
  
    // Note - str[i..n] is sorted
    // in ascending order Find
    // rightmost element's index
    // that is less than str[i - 1]
    let j = i - 1;
    while (j + 1 <= n && str[j + 1] < str[i - 1]){
        j++;
    }
     
    // Swap character at i-1 with j
    const temper = str[i - 1];
    str[i - 1] = str[j];
    str[j] = temper;
     
    // Reverse the substring [i..n]
    let size = n-i+1;
    for (let idx = 0; idx < Math.floor(size / 2); idx++) {
        let temp = str[idx + i];
        str[idx + i] = str[n - idx];
        str[n - idx] = temp;
    }
     
    return true;
}
 
// Function to print all the power set
function printPowerSet(set, n){  
 
    let contain = new Array(n).fill(0);
 
    // Empty subset
    document.write("<br>");
    for(let i = 0; i < n; i++){
        contain[i] = 1;
         
        // To avoid changing original 'contain'
        // array creating a copy of it i.e.
        // "Contain"
        let Contain = new Array(n);
        for(let indx = 0; indx < n; indx++){
            Contain[indx] = contain[indx];
        }
 
        // All permutation
        do{
            for(let j = 0; j < n; j++){               
                if(Contain[j]){
                    document.write(set[j]);
                } 
            }
            document.write("<br>");
             
        } while(prev_permutation(Contain));
    }
}
 
/*Driver code*/
const set = ['a','b','c'];
printPowerSet(set, 3);
 
// This code is contributed by Gautam goel (gautamgoel962)
Producción

a
b
c
ab
ac
bc
abc

Complejidad de Tiempo: O(n2 n )
Espacio Auxiliar: O(n)

Método 3: 
este método es específico del lenguaje de programación python. Podemos iterar un bucle sobre 0 hasta la longitud del conjunto para obtener y generar todas las combinaciones posibles de esa string con la longitud iterable. El siguiente programa dará la implementación de la idea anterior. 
 

A continuación se muestra la implementación del enfoque anterior.

Python3

#Python program to find powerset
from itertools import combinations
def print_powerset(string):
    for i in range(0,len(string)+1):
        for element in combinations(string,i):
            print(''.join(element))
string=['a','b','c']
print_powerset(string)
Producción

a
b
c
ab
ac
bc
abc

Método 4:

Podemos usar backtrack aquí, tenemos dos opciones primero considerar ese elemento y luego no considerar ese elemento. 

A continuación se muestra la implementación del enfoque anterior.

C++

#include <bits/stdc++.h>
using namespace std;
 
void findPowerSet(char* s, vector<char> &res, int n){
        if (n == 0) {
            for (auto i: res)
              cout << i;
            cout << "\n";
            return;
             
        }
         res.push_back(s[n - 1]);
         findPowerSet(s, res, n - 1);
         res.pop_back();                   
         findPowerSet(s, res, n - 1);
    }
     
void printPowerSet(char* s, int n){
    vector<char> ans;
    findPowerSet(s, ans, n);
}
 
 
int main()
{
    char set[] = { 'a', 'b', 'c' };
    printPowerSet(set, 3);
    return 0;
}

Java

import java.util.*;
  
class Main
{
    public static void findPowerSet(char []s, Deque<Character> res,int n){
        if (n == 0){
          for (Character element : res)
             System.out.print(element);
          System.out.println();
            return;
        }
        res.addLast(s[n - 1]);
        findPowerSet(s, res, n - 1);
        res.removeLast();                   
        findPowerSet(s, res, n - 1);
    }
  
    public static void main(String[] args)
    {
        char []set = {'a', 'b', 'c'};
        Deque<Character> res = new ArrayDeque<>();
        findPowerSet(set, res, 3);
    }
}

Python3

# Python3 program to implement the approach
 
# Function to build the power sets
def findPowerSet(s, res, n):
    if (n == 0):
        for i in res:
            print(i, end="")
        print()
        return
 
    # append the subset to result
    res.append(s[n - 1])
    findPowerSet(s, res, n - 1)
    res.pop()
    findPowerSet(s, res, n - 1)
 
# Function to print the power set
def printPowerSet(s, n):
    ans = []
    findPowerSet(s, ans, n)
 
# Driver code
set = ['a', 'b', 'c']
printPowerSet(set, 3)
 
# This code is contributed by phasing17

C#

// C# code to implement the approach
 
using System;
using System.Collections.Generic;
 
class GFG
{
    // function to build the power set
    public static void findPowerSet(char[] s,
                                    List<char> res, int n)
    {
 
        // if the end is reached
        // display all elements of res
        if (n == 0) {
            foreach(var element in res)
                Console.Write(element);
            Console.WriteLine();
            return;
        }
 
        // append the subset to res
        res.Add(s[n - 1]);
        findPowerSet(s, res, n - 1);
        res.RemoveAt(res.Count - 1);
        findPowerSet(s, res, n - 1);
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        char[] set = { 'a', 'b', 'c' };
        List<char> res = new List<char>();
 
        // Function call
        findPowerSet(set, res, 3);
    }
}
 
// This code is contributed by phasing17

Javascript

// JavaScript program to implement the approach
 
// Function to build the power sets
function findPowerSet(s, res, n)
{
    if (n == 0)
    {
        for (var i of res)
            process.stdout.write(i + "");
        process.stdout.write("\n");
        return;
    }
 
    // append the subset to result
    res.push(s[n - 1]);
    findPowerSet(s, res, n - 1);
    res.pop();
    findPowerSet(s, res, n - 1);
}
 
// Function to print the power set
function printPowerSet(s, n)
{
    let ans = [];
    findPowerSet(s, ans, n);
}
 
 
// Driver code
let set = ['a', 'b', 'c'];
printPowerSet(set, 3);
 
 
// This code is contributed by phasing17
Producción

cba
cb
ca
c
ba
b
a

Complejidad del tiempo: O(n2^n)

Complejidad espacial: O(n)

Programa recursivo para generar conjuntos de potencia
Consulte Conjunto de potencia en Java para la implementación en Java y más métodos para imprimir conjuntos de potencia.
Referencias:  
http://en.wikipedia.org/wiki/Power_set
 

Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

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