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

Тема в разделе "C и С++ FAQ", создана пользователем Sanek, 26 май 2004.

Статус темы:
Закрыта.
  1. Sanek

    Sanek Гость

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

    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);
    }
     
  3. klizardin

    klizardin Гость

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

    template<int N>
    class BitSet:public 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::eek:perator++();}
    else bit = true;
    }

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

    ostream& output(ostream& out)
    {
    out<<bit?'1':'0';
    return base::eek: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>();
    }
     
  4. Гость

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

    Решение номер раз: N-разрядный булев вектор как ]N/8[-разрядный вектор байтов (или ]N/32[-разрядный вектор двордов...)
    Код (Text):
    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>
    Код (Text):
    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;
    }
     
Загрузка...
Статус темы:
Закрыта.

Поделиться этой страницей