Encontrar todos los subconjuntos de un conjunto

Necesito un algoritmo para encontrar todos los subconjuntos de un conjunto donde el número de elementos en un conjunto es n .

 S={1,2,3,4...n} 

Editar: Tengo problemas para entender las respuestas proporcionadas hasta el momento. Me gustaría tener ejemplos paso a paso de cómo funcionan las respuestas para encontrar los subconjuntos.

Por ejemplo,

 S={1,2,3,4,5} 

¿Cómo sabes que {1} y {1,2} son subconjuntos?

Podría alguien ayudarme con una función simple en c ++ para encontrar subconjuntos de {1,2,3,4,5}

Es muy simple de hacer esto recursivamente. La idea básica es que para cada elemento, el conjunto de subconjuntos se puede dividir por igual en aquellos 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 este. Para uno de ellos, agregue n a cada subconjunto. Luego tome la unión de las dos copias.

Editar Para que quede 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 parece fácil aquí:

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

2) Obtenga una representación binaria de 2 ^ n.
Eg. 8 in binary is 1000

3) Ir de 0 a (2 ^ n – 1). En cada iteración, para cada 1 en la representación binaria, forma un subconjunto con elementos que corresponden 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) Haz una unión de todos los subconjuntos encontrados en el paso 3. Devuelve.
Eg. Simple union of above sets!

En caso de que alguien más venga y todavía se esté preguntando, 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; for (int j = 0; j < subsetTemp.size(); j++) subsetTemp[j].push_back( set[i] ); for (int j = 0; j < subsetTemp.size(); j++) subset.push_back( subsetTemp[j] ); } 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 utilizar un set lugar de un vector (que utilicé para evitar los iteradores en el código).

Si desea enumerar todos los subconjuntos posibles, eche un vistazo a este documento. Discuten diferentes enfoques, como el orden lexicográfico, la encoding gris y la secuencia del banquero. Dan una implementación de ejemplo de la secuencia del banquero y discuten diferentes características de las soluciones, por ejemplo, el rendimiento.

Aquí, lo he explicado en detalle. Haga upvote, si le gusta el blogpost.

http://cod3rutopia.blogspot.in/

De todos modos, si no puede encontrar mi blog aquí, está la explicación.

Es un problema que es de naturaleza recursiva.

Esencialmente para que un elemento esté presente en un subconjunto, hay 2 opciones:

1) Está presente en el conjunto

2) Está ausente en el set.

Esta es la razón por la cual un conjunto de n números tiene 2 ^ n subconjuntos. (2 opciones por elemento)

Aquí está el pseudocódigo (C ++) para imprimir todos los subconjuntos seguidos por un ejemplo que explica cómo funciona el código. 1) A [] es la matriz de números cuyos subconjuntos quieres descubrir. 2) bool a [] es la matriz de booleanos donde a [i] indica si el número A [i] está presente en el conjunto o no.

 print(int A[],int low,int high) { if(low>high) { for(all entries i in bool a[] which are true) print(A[i]) } else {set a[low] to true //include the element in the subset print(A,low+1,high) set a[low] to false//not including the element in the subset print(A,low+1,high) } } 

No tiene que meterse con la recursividad y otros algoritmos complejos. Puede encontrar todos los subconjuntos usando patrones de bits (de decimal a binario) de todos los números entre 0 y 2 ^ (N-1). Aquí N es cardinalidad o número de elementos en ese conjunto. La técnica se explica aquí con una implementación y demostración.

http://codeding.com/?article=12

Aquí hay un algoritmo recursivo simple en python para encontrar todos los subconjuntos de un conjunto:

 def find_subsets(so_far, rest): print 'parameters', so_far, rest if not rest: print so_far else: find_subsets(so_far + [rest[0]], rest[1:]) find_subsets(so_far, rest[1:]) find_subsets([], [1,2,3]) 

El resultado será el siguiente: $ python subconjuntos.py

 parameters [] [1, 2, 3] parameters [1] [2, 3] parameters [1, 2] [3] parameters [1, 2, 3] [] [1, 2, 3] parameters [1, 2] [] [1, 2] parameters [1] [3] parameters [1, 3] [] [1, 3] parameters [1] [] [1] parameters [] [2, 3] parameters [2] [3] parameters [2, 3] [] [2, 3] parameters [2] [] [2] parameters [] [3] parameters [3] [] [3] parameters [] [] [] 

Mire el siguiente video de Stanford para obtener una buena explicación de este algoritmo:

 https://www.youtube.com/watch?v=NdF1QDTRkck&feature=PlayList&p=FE6E58F856038C69&index=9 

Aquí hay una solución en Scala:

 def subsets[T](s : Set[T]) : Set[Set[T]] = if (s.size == 0) Set(Set()) else { val tailSubsets = subsets(s.tail); tailSubsets ++ tailSubsets.map(_ + s.head) } 

Aquí hay un pseudocódigo. Puede cortar las mismas llamadas recursivas almacenando los valores de cada llamada sobre la marcha y antes de la comprobación recursiva de llamadas si el valor de la llamada ya está presente.

El siguiente algoritmo tendrá todos los subconjuntos excluyendo el conjunto vacío.

 list * subsets(string s, list * v){ if(s.length() == 1){ list.add(s); return v; } else { list * temp = subsets(s[1 to length-1], v); int length = temp->size(); for(int i=0;i 

Aquí hay un código de trabajo que escribí hace algún tiempo

 // Return all subsets of a given set #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef vector vi; typedef vector vll; typedef vector< vector > vvi; typedef vector vs; vvi get_subsets(vi v, int size) { if(size==0) return vvi(1); vvi subsets = get_subsets(v,size-1); vvi more_subsets(subsets); for(typeof(more_subsets.begin()) it = more_subsets.begin(); it !=more_subsets.end(); it++) { (*it).push_back(v[size-1]); } subsets.insert(subsets.end(), (more_subsets).begin(), (more_subsets).end()); return subsets; } int main() { int ar[] = {1,2,3}; vi v(ar , ar+int(sizeof(ar)/sizeof(ar[0]))); vvi subsets = get_subsets(v,int((v).size())); for(typeof(subsets.begin()) it = subsets.begin(); it !=subsets.end(); it++) { printf("{ "); for(typeof((*it).begin()) it2 = (*it).begin(); it2 !=(*it).end(); it2++) { printf("%d,",*it2 ); } printf(" }\n"); } printf("Total subsets = %d\n",int((subsets).size()) ); } 

Abajo, con la solución espacial O (n)

 #include  void print_all_subset(int *A, int len, int *B, int len2, int index) { if (index >= len) { for (int i = 0; i < len2; ++i) { printf("%d ", B[i]); } printf("\n"); return; } print_all_subset(A, len, B, len2, index+1); B[len2] = A[index]; print_all_subset(A, len, B, len2+1, index+1); } int main() { int A[] = {1, 2, 3, 4, 5, 6, 7}; int B[7] = {0}; print_all_subset(A, 7, B, 0, 0); } 

Aquí hay una implementación de la solución de Michael para cualquier tipo de elemento en std :: vector.

 #include  #include  using std::vector; using std::cout; using std::endl; // Find all subsets template vector< vector > subsets(const vector& set) { // Output vector< vector > ss; // If empty set, return set containing empty set if (set.empty()) { ss.push_back(set); return ss; } // If only one element, return itself and empty set if (set.size() == 1) { vector empty; ss.push_back(empty); ss.push_back(set); return ss; } // Otherwise, get all but last element vector allbutlast; for (unsigned int i=0;i<(set.size()-1);i++) { allbutlast.push_back( set[i] ); } // Get subsets of set formed by excluding the last element of the input set vector< vector > ssallbutlast = subsets(allbutlast); // First add these sets to the output for (unsigned int i=0;i a; a.push_back('a'); a.push_back('b'); a.push_back('c'); vector< vector > sa = subsets(a); for (unsigned int i=0;i 

Salida:

 (empty line) a b ab c ac bc abc 

una forma simple sería el siguiente pseudo código:

 Set getSubsets(Set theSet) { SetOfSets resultSet = theSet, tempSet; for (int iteration=1; iteration < theSet.length(); iteration++) foreach element in resultSet { foreach other in resultSet if (element != other && !isSubset(element, other) && other.length() >= iteration) tempSet.append(union(element, other)); } union(tempSet, resultSet) tempSet.clear() } } 

Bueno, no estoy del todo seguro de que esto sea correcto, pero se ve bien.

aquí está mi solución recursiva.

 vector > getSubsets(vector a){ //base case //if there is just one item then its subsets are that item and empty item //for example all subsets of {1} are {1}, {} if(a.size() == 1){ vector > temp; temp.push_back(a); vector b; temp.push_back(b); return temp; } else { //here is what i am doing // getSubsets({1, 2, 3}) //without = getSubsets({1, 2}) //without = {1}, {2}, {}, {1, 2} //with = {1, 3}, {2, 3}, {3}, {1, 2, 3} //total = {{1}, {2}, {}, {1, 2}, {1, 3}, {2, 3}, {3}, {1, 2, 3}} //return total int last = a[a.size() - 1]; a.pop_back(); vector > without = getSubsets(a); vector > with = without; for(int i=0;i > total; for(int j=0;j 

una simple máscara de bits puede hacer el truco como se discutió antes … por rgamber

 #include #include #define pf printf #define sf scanf using namespace std; void solve(){ int t; char arr[99]; cin >> t; int n = t; while( t-- ) { for(int l=0; l> arr[l]; for(int i=0; i<(1< 

Para aquellos que quieren una implementación simple usando std :: vector y std :: set para el algoritmo de Michael Borgwardt:

 // Returns the subsets of given set vector > subsets(set s) { vector > s1, s2; set empty; s1.push_back(empty); // insert empty set // iterate over each element in the given set for(set::iterator it=s.begin(); it!=s.end(); ++it) { s2.clear(); // clear all sets in s2 // create subsets with element (*it) for(vector >::iterator s1iter=s1.begin(); s1iter!=s1.end(); ++s1iter) { set temp = *s1iter; temp.insert(temp.end(), *it); s2.push_back(temp); } // update s1 with new sets including current *it element s1.insert(s1.end(), s2.begin(), s2.end()); } // return return s1; } 

Esta pregunta es vieja. Pero hay una solución recursiva simple y elegante para el problema de OP.

 using namespace std; void recsub(string sofar, string rest){ if(rest=="") cout<