boost::dynamic_bitsetでn-集合するNset_iterator
前回*1の続きというか
n-集合ってのは集合Xの中からn個だけ取り出したものの集合のことでこれが正式名称でいいのかわからん。nCk集合とかそっちの方がよかったのかしら
n-setはべき集合ほどではないにしてもモリモリと要素が増えるので
(n～n!/(n/2)!^2)
前回同様イテレータで何とかする
template<class T,class SET=std::set<T>>
class Nset_iterator
{
public:
template<class Iter>
Nset_iterator(const Iter&begin,const Iter&end,size_t k)
:data(begin,end),bit(data.size()),k(k),endflag(false)
{
if(bit.size()<k)throw std::logic_error("k>n");
for(size_t i=0;i<k;++i)
bit.set(bit.size()-1-i);
}
Nset_iterator()
:endflag(true),k(0)
{}
SET operator*()
{
std::vector<T> temp;
temp.reserve(k);
for(auto it=bit.find_first();it!=bit.npos;it=bit.find_next(it))
temp.push_back(data.at(it));
return SET(temp.begin(),temp.end());
}
const Nset_iterator& operator++()
{
_incsub();
return *this;
}
bool operator!=(const Nset_iterator&rhs)const
{
if(endflag^rhs.endflag) return true;
if(endflag) return false;
return bit!=rhs.bit||data!=rhs.data;
}
bool operator==(const Nset_iterator&rhs)const
{
return !(*this!=rhs);
}
private:
void _incsub()
{
size_t end=0;
size_t n=0;
auto it=bit.find_first();
for(;it!=bit.npos;it=bit.find_next(it))
{
if(it==end)
{
bit.set(it,false);
++end;
++n;
}
else
{
bit.set(it,false).set(it-1,true);
for(size_t i=0;i<n;++i)
bit.set((it-1)-1-i);
return;
}
}
endflag=true;
}
std::vector<T> data;
boost::dynamic_bitset<> bit;
bool endflag;
size_t k;
};
//使い方
std::vector<int> v;
for(size_t i=0;i<5;++i)
v.push_back(i);
Nset_iterator<int> it(v.begin(),v.end(),3),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: 2 3 4
1: 1 3 4
2: 0 3 4
3: 1 2 4
4: 0 2 4
5: 0 1 4
6: 1 2 3
7: 0 2 3
8: 0 1 3
9: 0 1 2
とりあえず0~4の中から3つとり出している
総数は5C3=5P3/3!=10
