¿Cómo encontrar todos los subconjuntos posibles de una matriz determinada?

Question

Quiero extraer todos los subconjuntos posibles de una matriz en C# o C++ y luego calcular la suma de todos los elementos respectivos de las matrices subconjuntos para verificar cuántos de ellos son iguales a un número dado.

Lo que estoy buscando es el algoritmo. Entiendo la lógica aquí, pero no he podido implementar esta ahora.

Answer 1

Considerando un conjunto S de elementos, y un subconjunto dado, cada elemento pertenece o no pertenece a ese subconjunto. Por lo tanto, son 2^N posibles subconjuntos (si incluye los conjuntos original y vacío), y hay una asignación directa de los bits en la representación binaria x entre 0 y 2^N a los elementos en el x del subconjunto x.

Una vez que haya resuelto cómo enumerar los elementos de un subconjunto dado, agregar los valores es simple.

Para encontrar subconjuntos, que equivalen a un total t para grandes N, una optimización sería registrar esos subconjuntos que excedan t, y no prueba ninguna que son propios de los superseries. Comprobando si el conjunto de números x es un superconjunto del conjunto y se puede lograr con una única operación a nivel de bits y una comparación entera.

Answer 2

¿Usted;

A) ¿Realmente desea encontrar todos los subconjuntos posibles?

o

B) desea conocer cuántos elementos de una matriz se pueden combinar para ser igual a un número dado, y ver A) como un paso hacia la solución?

Si es A), entonces es bastante sencillo, pero el número de subconjuntos posibles se vuelve ridículamente grande muy rápidamente.

Si es B), primero debe ordenar la matriz y trabajar desde allí.

Answer 3

Ha sido uno de mis proyectos universitarios hace 4/5 años, y no puedo recordar bien el algoritmo. Como veo & mi memoria sirve que está usando una matriz como el conjunto original y una máscara de bits para indicar qué elementos están presentes en el subconjunto actual.
Aquí está el código anti-probado del archivo:

#include <iostream> 

#ifndef H_SUBSET 
#define H_SUBSET 

template <class T> 
class Subset { 
    private: 
     int Dimension; 
     T *Set; 
     bool *Bitmask; 
    public: 
     Subset(T *set, int dim); 
     ~Subset(void); 
     void Show(void); 
     void NextSubset(void); 
     void EmptySet(void); 
     void FullSet(void); 
     int SubsetCardinality(void); 
     int SetCardinality(void); 
     T operator[](int index); 
};  

template <class T> 
int Subset<T>::SetCardinality(void) { 
    return Dimension; 
} 

template <class T> 
int Subset<T>::SubsetCardinality(void) { 
    int dim = 0; 
    for(int i = 0; i<Dimension; i++) { 
     if(Bitmask[i]) { 
      dim++; 
     } 
    } 
    return dim; 
} 

template <class T> 
void Subset<T>::EmptySet(void) { 
    for(int i = 0; i<Dimension; i++) { 
     Bitmask[i] = 0; 
    } 
    return; 
} 

template <class T> 
void Subset<T>::FullSet(void) { 
    for(int i = 0; i<Dimension; i++) { 
     Bitmask[i] = 1; 
    } 
    return; 
} 

template <class T> 
void Subset<T>::NextSubset(void) { 
    int i = Dimension - 1; 
    while(!Bitmask[i]&&i>=0) { 
     i--; 
     if(i<0) { 
      break; 
     } 
    } 
    if(i>=0) { 
     Bitmask[i] = !Bitmask[i]; 
    } 
    for(int j = i+1; j < Dimension; j++) { 
     Bitmask[j] = !Bitmask[j]; 
    } 
    return; 
} 

template <class T> 
void Subset<T>::Show(void) { 
    std::cout << "{ "; 
    for(int i=0; i<Dimension; i++) { 
     if(Bitmask[i]) { 
      std::cout << Set[i] << ", "; 
     } 
    } 
    std::cout << "}"; 
    return; 
} 

template <class T> 
Subset<T>::Subset(T *set, int dim) { 
    Set = new T[dim]; 
    Bitmask = new bool[dim]; 
    Dimension = dim; 
    for(int i=0; i<dim; i++) { 
     Set[i] = set[i]; 
     Bitmask[i] = true; 
    } 
} 

template <class T> 
Subset<T>::~Subset(void) { 
    delete [] Set; 
    delete [] Bitmask; 
} 
#endif // H_SUBSET 

Y si es su tarea, estás matando bro;)

Answer 4

Lo que estás buscando se llama la power set. Rosetta Code tiene muchas implementaciones diferentes, pero aquí está su código C++ (usan un vector en lugar de una matriz, pero debería ser bastante fácil de traducir).

#include <iostream> 
#include <set> 
#include <vector> 
#include <iterator> 

typedef std::set<int> set_type; 
typedef std::set<set_type> powerset_type; 

powerset_type powerset(set_type const& set) 
{ 
    typedef set_type::const_iterator set_iter; 
    typedef std::vector<set_iter> vec; 
    typedef vec::iterator vec_iter; 

    struct local 
    { 
    static int dereference(set_iter v) { return *v; } 
    }; 

    powerset_type result; 

    vec elements; 
    do 
    { 
    set_type tmp; 
    std::transform(elements.begin(), elements.end(), 
        std::inserter(tmp, tmp.end()), 
        local::dereference); 
    result.insert(tmp); 
    if (!elements.empty() && ++elements.back() == set.end()) 
    { 
     elements.pop_back(); 
    } 
    else 
    { 
     set_iter iter; 
     if (elements.empty()) 
     { 
     iter = set.begin(); 
     } 
     else 
     { 
     iter = elements.back(); 
     ++iter; 
     } 
     for (; iter != set.end(); ++iter) 
     { 
     elements.push_back(iter); 
     } 
    } 
    } while (!elements.empty()); 

    return result; 
} 

int main() 
{ 
    int values[4] = { 2, 3, 5, 7 }; 
    set_type test_set(values, values+4); 

    powerset_type test_powerset = powerset(test_set); 

    for (powerset_type::iterator iter = test_powerset.begin(); 
     iter != test_powerset.end(); 
     ++iter) 
    { 
    std::cout << "{ "; 
    char const* prefix = ""; 
    for (set_type::iterator iter2 = iter->begin(); 
     iter2 != iter->end(); 
     ++iter2) 
    { 
     std::cout << prefix << *iter2; 
     prefix = ", "; 
    } 
    std::cout << " }\n"; 
    } 
} 

Salida:

{ } 
{ 2 } 
{ 2, 3 } 
{ 2, 3, 5 } 
{ 2, 3, 5, 7 } 
{ 2, 3, 7 } 
{ 2, 5 } 
{ 2, 5, 7 } 
{ 2, 7 } 
{ 3 } 
{ 3, 5 } 
{ 3, 5, 7 } 
{ 3, 7 } 
{ 5 } 
{ 5, 7 } 
{ 7 }