boost::Multiprecisionでべき集合する PowerSet_iterator
先日諸用でべき集合*1が必要になったので色々考えてみた
普通に考えてべき集合って集合の集合だから
とかやればいいんだけどべき集合って2^Xの表記通り要素数が２^[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からいくつか適当に要素をとってきたものの集合の集まりである
