Come trovare tutti i sottoinsiemi possibili di un determinato array?

Question

Voglio estrarre tutti i possibili sottoinsiemi di una matrice in C# o C++ e quindi calcolare la somma di tutti i rispettivi elementi degli array di sottoinsieme per verificare quanti di essi sono uguali a un determinato numero.

Quello che sto cercando è l'algoritmo. Capisco la logica qui, ma non sono stato in grado di implementarlo ora.

Answer 1

Considerando un set S di N elementi e un determinato sottoinsieme, ciascun elemento appartiene o non appartiene a tale sottoinsieme. Pertanto sono 2^N sottoinsiemi possibili (se si includono i set originali e vuoti) e c'è una mappatura diretta dai bit nella rappresentazione binaria di x tra 0 e 2^N per gli elementi nel x sottoinsieme di S.

Una volta elaborato come enumerare gli elementi di un determinato sottoinsieme, l'aggiunta dei valori è semplice.

per la ricerca di sottoinsiemi che eguagliano un totale t per grandi N, un'ottimizzazione potrebbe essere quello di registrare i sottoinsiemi che superano t, e non prova alcuna che sono propri superset di quelle. È possibile verificare se il set è un superset del set con un'operazione a singolo bit e confronto di numeri interi.

Answer 2

Sì;

A) Vuoi davvero trovare tutti i possibili sottoinsiemi?

o

B) desidera trovare quanti elementi dell'array possono essere combinati per uguagliare un dato numero, e vedi A) come un passo verso la soluzione?

Se è A), allora è abbastanza semplice ma il numero di sottoinsiemi possibili diventa ridicolmente grande molto rapidamente.

Se è B), è necessario ordinare prima l'array e lavorare da lì.

Answer 3

È stato uno dei miei progetti universitari 4/5 anni fa e non riesco a ricordare bene l'algoritmo. Come vedo & la mia memoria serve sta usando un array come set originale e una maschera di bit per indicare quali elementi sono presenti nel sottoinsieme corrente.
Ecco il codice non-testato dall'archivio:

#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 

E se è il vostro lavoro, si sta uccidendo te stesso bro;)

Answer 4

Quello che stai cercando è chiamato il power set. Rosetta Code ha un sacco di differenti implementazioni, ma ecco il loro codice C++ (usano un vettore invece di un array, ma dovrebbe essere abbastanza facile da tradurre).

#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"; 
    } 
} 

uscita:

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