c++ - tiene - teoria de conjuntos ejercicios

Encontrar todos los subconjuntos de un conjunto

Question

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}

Answer 1

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<<sofar<<endl;
  else{
    recsub(sofar+rest[0], rest.substr(1)); //including first letter
    recsub(sofar, rest.substr(1)); //recursion without including first letter.
  }
}
void listsub(string str){
  recsub("",str);
}
int main(){
  listsub("abc");
  return 0;
}

//output
abc
ab
ac
a
bc
b
c

//end: there''s a blank output too representing empty subset

Answer 2

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

#include <stdio.h>

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);
}

Answer 3

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

Answer 4

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

// Return all subsets of a given set
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<sstream>
#include<cstring>
#include<climits>
#include<cmath>
#include<iterator>
#include<set>
#include<map>
#include<stack>
#include<queue>
using namespace std;


typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector< vector<int> > vvi;
typedef vector<string> 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()) );
}

Answer 5

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<length;i++){
            temp.add(s[0]+temp[i]);
        }

        list.add(s[0]);
        return temp;
    }
}

Answer 6

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

#include <iostream>
#include <vector>

using std::vector;
using std::cout;
using std::endl;

// Find all subsets
template<typename element>
vector< vector<element> > subsets(const vector<element>& set)
{
  // Output
  vector< vector<element> > 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<element> empty;
    ss.push_back(empty);
    ss.push_back(set);
    return ss;
  }

  // Otherwise, get all but last element
  vector<element> 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<element> > ssallbutlast = subsets(allbutlast);
  // First add these sets to the output
  for (unsigned int i=0;i<ssallbutlast.size();i++) {
    ss.push_back(ssallbutlast[i]);
  }
  // Now add to each set in ssallbutlast the last element of the input
  for (unsigned int i=0;i<ssallbutlast.size();i++) {
    ssallbutlast[i].push_back( set[set.size()-1] );
  }
  // Add these new sets to the output
  for (unsigned int i=0;i<ssallbutlast.size();i++) {
    ss.push_back(ssallbutlast[i]);
  }

  return ss;

}

// Test
int main()
{

  vector<char> a;
  a.push_back(''a'');
  a.push_back(''b'');
  a.push_back(''c'');


  vector< vector<char> > sa = subsets(a);

  for (unsigned int i=0;i<sa.size();i++) {
    for (unsigned int j=0;j<sa[i].size();j++) {
      cout << sa[i][j];
    }
    cout << endl;
  }

  return 0;

}

Salida:

(empty line)
a
b
ab
c
ac
bc
abc

Answer 7

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) 
} 

Answer 8

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)
   }  
  }  

Answer 9

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!

Answer 10

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<int> > getAllSubsets(vector<int> set)
{
    vector< vector<int> > subset;
    vector<int> empty;
    subset.push_back( empty );

    for (int i = 0; i < set.size(); i++)
    {
        vector< vector<int> > 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).

Answer 11

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

Answer 12

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

Answer 13

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<set<int> > subsets(set<int> s) {
    vector<set<int> > s1, s2;
    set<int> empty;
    s1.push_back(empty); // insert empty set
    // iterate over each element in the given set
    for(set<int>::iterator it=s.begin(); it!=s.end(); ++it) {
        s2.clear(); // clear all sets in s2
        // create subsets with element (*it)
        for(vector<set<int> >::iterator s1iter=s1.begin(); s1iter!=s1.end(); ++s1iter) {
            set<int> 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;
}

Answer 14

Si desea enumerar todos los subconjuntos posibles, eche un vistazo a this documento. Discuten diferentes enfoques, como el orden lexicográfico, la codificación 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.

Answer 15

aquí está mi solución recursiva.

vector<vector<int> > getSubsets(vector<int> 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<vector<int> > temp;
        temp.push_back(a);

        vector<int> 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<vector<int> > without = getSubsets(a);

        vector<vector<int> > with = without;

        for(int i=0;i<without.size();i++){

            with[i].push_back(last);

        }

        vector<vector<int> > total;

        for(int j=0;j<without.size();j++){
            total.push_back(without[j]);
        }

        for(int k=0;k<with.size();k++){
            total.push_back(with[k]);
        }


        return total;
    }


}

Answer 16

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.

Answer 17

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

#include<iostream>
#include<cstdio>

#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<n; l++) cin >> arr[l];
                for(int i=0; i<(1<<n); i++)
                {
                    for(int j=0; j<n; j++)
                        if(i & (1 << j))
                        pf("%c", arr[j]);
                    pf("/n");
                }
            }
        }

int main() {
      solve();
      return 0;
}