読者です 読者をやめる 読者になる 読者になる

boost::Multiprecisionでべき集合する PowerSet_iterator

C++ boost

先日諸用でべき集合*1が必要になったので色々考えてみた

普通に考えてべき集合って集合の集合だから

set<set<T>> MakePowerSet(Iterator begin,Iterator end)

 とかやればいいんだけどべき集合って2^Xの表記通り要素数が2^[Xの要素数]になるからxが10個あるとそれだけでべき集合は1024

そしてそれぞれの集合に平均5個の要素が入っていてる訳でそれはそれはもう大変なわけなのですよ

Xの要素数をnとして

[使用バイト数]=(2^n)*(sizeof(set<T>)+(n/2)*sizeof(T))

 Tをint,nを10とした場合28672byteだそうで。たったの10でおよそ28kByteですよ

これがn=20だとオーバーフローしてもう表示もできませんよ

 

そんなわけで逐次逐次生成していく必要があるわけでIteratorにする必要があるわけで

 

#include<set>
#include<boost\multiprecision\cpp_int.hpp>

template<class T,class Set=std::set<T>>
class PowerSet_iterator
{
public:
    PowerSet_iterator()
        :x(1)
    {}
    template<class Iter>
    PowerSet_iterator(const Iter&begin,const Iter&end)
        :data(begin,end),x(0)
    {}
    Set operator*()
    {
        if(bittest(data.size()))
            throw std::out_of_range("");
        std::vector<T> temp;
        for(size_t i=0;i<data.size();++i)
        {
            if(bittest(i))
                temp.push_back(data[i]);
        }
        return Set(temp.begin(),temp.end());
    }
    const PowerSet_iterator& operator++()
    {
        if(bittest(data.size()))
            throw std::out_of_range("");
        ++x;
        return *this;
    }
    PowerSet_iterator operator++(int)
    {
        auto self=*this;
        ++*this;
        return self;
    }
    bool operator!=(const PowerSet_iterator&rhs)const
    {
        bool l=bittest(data.size());
        bool r=rhs.bittest(rhs.data.size());
        if(l^r)return true;       
        else if(l) return false;
        else
            return data!=rhs.data||x!=rhs.x;
    }
    bool operator==(const PowerSet_iterator&rhs)const
    {
        return !(*this!=rhs);
    }
private:
    boost::multiprecision::cpp_int x;
    const std::vector<T> data;
    bool bittest(unsigned int i)const
    {
        namespace mp=boost::multiprecision;
        return mp::bit_test(x,i);
    }

};

 

boostの可変長のbitset使おうかと思ったけどこっちはインクリメントあるし多倍超変数なんか使いたかったし

 

//main

std::set<std::string> v;
    v.insert("cat");
    v.insert("dog");
    v.insert("bird");
    v.insert("rabbit");
    v.insert("bunny");
    PowerSet_iterator<std::string> it(v.begin(),v.end());
    PowerSet_iterator<std::string> end;

    size_t i=0;
    for(;it!=end;++it)
    {
        std::cout<<i<<":\t";
        for(auto&x:*it)
            std::cout<<x<<"\t";
        std::cout<<std::endl;
        ++i;
    }

 

//結果

0:
1:      bird
2:      bunny
3:      bird    bunny
4:      cat
5:      bird    cat
6:      bunny   cat
7:      bird    bunny   cat
8:      dog
9:      bird    dog
10:     bunny   dog
11:     bird    bunny   dog
12:     cat     dog
13:     bird    cat     dog
14:     bunny   cat     dog
15:     bird    bunny   cat     dog
16:     rabbit
17:     bird    rabbit
18:     bunny   rabbit
19:     bird    bunny   rabbit
20:     cat     rabbit
21:     bird    cat     rabbit
22:     bunny   cat     rabbit
23:     bird    bunny   cat     rabbit
24:     dog     rabbit
25:     bird    dog     rabbit
26:     bunny   dog     rabbit
27:     bird    bunny   dog     rabbit
28:     cat     dog     rabbit
29:     bird    cat     dog     rabbit
30:     bunny   cat     dog     rabbit
31:     bird    bunny   cat     dog     rabbit

 

VS2012のdebugだとどうにもこうにもMultiprecisionが使い物にならないからreleaseにして使ってね

 

 

*1:べき集合ってのは要するに『集合の集合』でX={1,2,3...,10}とすると

Xのべき集合(2^Xで表す)は{{ },{1},{2},..{10},{1,2},{1,3},.....{1,2,3....,10}}

となる

つまりXからいくつか適当に要素をとってきたものの集合の集まりである