Encontrar todos los subconjuntos de un conjunto

Estuvimos indagado por distintos espacios para brindarte la respuesta para tu duda, si tienes preguntas déjanos tu duda y te respondemos sin falta.

Solución:

Es muy simple hacer esto recursivamente. La idea básica es que, para cada elemento, el conjunto de subconjuntos se puede dividir por igual en los que contienen ese elemento y los que no, y esos dos conjuntos son por lo demás iguales.

• Para n=1, el conjunto de subconjuntos es , 1
• Para n>1, encuentre el conjunto de subconjuntos de 1,…,n-1 y haga dos copias de él. Para uno de ellos, agregue n a cada subconjunto. Luego tome la unión de las dos copias.

Editar Para que quede muy claro:

• El conjunto de subconjuntos de 1 es , 1
• Para 1, 2, tome , 1, agregue 2 a cada subconjunto para obtener 2, 1, 2 y tome la unión con , 1 para obtener , 1, 2, 1, 2
• Repita hasta llegar a n

Demasiado tarde para responder, pero un enfoque iterativo suena fácil aquí:

1) para un conjunto de n elementos, obtenga el valor de 2^n. Habrá 2^n no. de subconjuntos. (2^n porque cada elemento puede estar presente (1) o ausente (0). Entonces, para n elementos habrá 2^n subconjuntos). P.ej:
for 3 elements, say a,b,c, there will be 2^3=8 subsets

2) Obtener una representación binaria de 2^n. P.ej:
8 in binary is 1000

3) Ir de 0 para (2^n - 1). En cada iteración, por cada 1 en la representación binaria, formar un subconjunto con elementos que correspondan al índice de ese 1 en la representación binaria. P.ej:

For the elements a, b, c
000 will give    
001 will give    c
010 will give    b
011 will give    b, c
100 will give    a
101 will give    a, c
110 will give    a, b
111 will give    a, b, c

4) Hacer una unión de todos los subconjuntos así encontrados en el paso 3. Volver. P.ej:
Simple union of above sets!

En caso de que alguien más venga y todavía se pregunte, aquí hay una función que usa la explicación de Michael en C++

vector< vector > getAllSubsets(vector set)

    vector< vector > subset;
    vector empty;
    subset.push_back( empty );

    for (int i = 0; i < set.size(); i++)
    
        vector< vector > subsetTemp = subset;  //making a copy of given 2-d vector.

        for (int j = 0; j < subsetTemp.size(); j++)
            subsetTemp[j].push_back( set[i] );   // adding set[i] element to each subset of subsetTemp. like adding 2(in 2nd iteration  to ,1 which gives 2,1,2.

        for (int j = 0; j < subsetTemp.size(); j++)
            subset.push_back( subsetTemp[j] );  //now adding modified subsetTemp to original subset (before,1 , after,1,2,1,2) 
    
    return subset;

Sin embargo, tenga en cuenta que esto devolverá un conjunto de tamaño 2^N con TODOS los subconjuntos posibles, lo que significa que posiblemente habrá duplicados. Si no quieres esto, te sugiero que uses un set en lugar de un vector(que usé para evitar iteradores en el código).

---

---

Utiliza Nuestro Buscador