Генерация подмножеств конечных множеств

[Sanek]

Народ, кто-нибудь помогите пожалуйста. Нужно реализовать на С++ алгоритм генерации всех подмножеств конечного множества. Млин, до зарезу нужно. Я примерно знаю как. Заведем массив B[0..n] из (n+1) элемента. B=0, если i-ый элемент в подмножество не входит,
и B=1 иначе. Т.о. пустому подмножеству будет соответствовать набор из n нулей,
а n-элементному подмножеству - набор из n единиц.
Алгоритм: будем генерировать числа от 0 до 2^n-1, находить их двоичное представление,
и формировать подмножество из элементов с индексами единичных битов в этом представлении.
Я бы может и сделал, но в С++ хреново понимаю.

 

[klizardin]

//ну что же пусть будет чьето дамашнее задание не думаю что это так нужно но всеже
//по твоему алгоритму
// ближе к сишному решение

#include <ostream>
#include <stdlib.h>
#include <string.h>

typedef unsigned int uint;
void output(
uint* mas// множество, как набор битов
,int n // изних заполенно n бит
)
{
int i,sz = (n+(sizeof(uint)<<3)-1)/(sizeof(uint)<<3);
uint maxbitmask = 1<<((n+1)%(sizeof(uint)<<3));
uint mask;
for(i=0;i<sz-1;i++)
{
for(mask=1;mask;mask<<=1)
cout<<((mas&mask)!=0)?'1':'0';
}
for(mask=1;mask!=maxbitmask;mask<<=1)
{
cout<<((mas[sz-1]&mask)!=0)?'1':'0';
}
cout<<endl;
}

typedef void (*OutputFunc)(uint*,int);

void build(
int n// размер множества
,OutputFunc outputfunc // функция для вывода полученного множества
)
{
int sz = (n+1+(sizeof(uint)<<3)-1)/(sizeof(uint)<<3);
uint* m = new uint[sz];
memset(m,0,sz*sizeof(uint));
int i;
uint maxbitmask = 1<<((n+1)%(sizeof(uint)<<3));
for(;(m[sz-1]&maxbitmask)==0// условие продолжения
{
//инкрементируем биты
(*outputfunc)(m,n);
for(i=0;i<sz;i++)
{
if(m)
{
if(!++m)continue;
}
else ++m;
break;
}
}
delete m;
}

void test1(
int n // размер множества
)
{
build(n,output);
}

 

[klizardin]

// потратил немного времени и вот тебе C++ вариант
//

template<int N>
class BitSetublic BitSet<N-1>
{
enum {BASE=N-1};
typedef BitSet<BASE> base;
protected:
bool bit;

public:

void clear()
{
bit = false;
base::clear();
}

void operator++()
{
if(bit) {bit=false;base:perator++();}
else bit = true;
}

operator bool()
{
return base:perator bool();
}

ostream& output(ostream& out)
{
out<<bit?'1':'0';
return base:utput(out);
}
// friend ostream& operator<<(ostream& out,BitSet<N>& bits);
};

template<>
class BitSet<0>
{
protected:
bool maxbit;
public:
void clear()
{
maxbit = false;
}

void operator++()
{
if(!maxbit) maxbit=true;
}

operator bool()
{
return maxbit;
}

ostream& output(ostream& out)
{
return out;
}
};

/*
ostream& operator<<(ostream* out,BitSet<N>& bits)
{
return bits.output(out);
}*/

template<int N>
void test2()
{
BitSet<N> _bitset;
_bitset.clear();
for(;!_bitset;++_bitset)
{
_bitset.output(cout);
cout<<endl;
}
}

void _test2()
{
test2<10>();
}

 

[Guest]

Будем представлять подмножества булевыми векторами.
Напишем процедуру next_boolvec, последовательно перебирающую векторы. Она устроена как многоразрядный счётчик.

Решение номер раз: N-разрядный булев вектор как ]N/8[-разрядный вектор байтов (или ]N/32[-разрядный вектор двордов...)

template<class E> // E - беззнаковый целый
bool next_boolvec(E* vec, size_t N) // N - мощность множества
{
const size_t B = sizeof(E) * CHAR_BIT; // размер элемента в битах
const size_t S0 = N/B, S1 = (N+B-1)/B; // размер вектора в элементах (полные и неполные соответственно)
const size_t B1 = N%B; // значащие биты последнего неполного элемента
size_t k;
for(k = 0; k < S0; ++k)
 if(++vec[k] != 0) return true; // в противном случае мы получили переполнение и делаем перенос
if(S1 == S0) return false; // последний разряд - полный
return ++vec[k] < (E(1) << B1); // проверяем на переполнение; если нет, то ещё есть куда инкрементировать
}

Решение номер два: std::vector<bool>

bool next_boolvec(std::vector<bool>& vec)
{
for(size_t k=0, n=vec.size(); k<n; ++k)
 if((vec[k] = !vec[k])) return true;
return false;
}