Comment trouver tous les sous-ensembles possibles d'un groupe donné?

En considérant un ensemble S de N éléments, et un sous-ensemble, chaque élément ne soit ou n'appartient pas à ce groupe. Donc 2^N les sous-ensembles possibles (si vous incluez l'original et vide), et il existe une correspondance entre les bits de la représentation binaire de x entre 0 et 2^N aux éléments de la xème sous-ensemble de S.

Une fois que vous avez travaillé sur la façon d'énumérer les éléments d'un sous-ensemble, en ajoutant les valeurs est simple.

Pour trouver des sous-ensembles qui égale un total t pour les grandes N, une optimisation pourrait être d'enregistrer les sous-ensembles qui dépassent t, et pas à tout épreuve qui leur sont propres supersets de ceux-ci. Tester si le nombre de jeu x est un sur-ensemble de l'ensemble y peut être réalisé avec une seule opération au niveau du bit et une comparaison des entiers.

OriginalL'auteur Pete Kirkham

C'est l'un de mes collège des projets de 4/5 ans, et je ne peux pas rappeler l'algorithme. Comme je vois que & ma mémoire est bonne c'est à l'aide d'un tableau que l'ensemble original et un masque de bits pour indiquer quels éléments sont présents dans les sous-ensemble.

voici le code non testé à partir de l'archive:

#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

Et si c'est votre devoir, vous tuez vous-même bro 😉

OriginalL'auteur sepehr