00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00037 #ifndef PARTITION_BOX_H
00038 #define PARTITION_BOX_H
00039
00040 using namespace std;
00041
00042 #include <iostream>
00043 #include <fstream>
00044 #include <vector>
00045 #include <cmath>
00046
00047 template <class Tpart> class Partition_box
00048 {
00049 protected :
00050
00052 vector< Tpart > _partition;
00054 vector< int > _nbpartition_with_nbelement;
00055
00057 bool ** _possib;
00059 int _nbposs;
00061 int * _pow;
00062
00064 short _size;
00065
00067 long _cardinal;
00068
00070 long _currpart;
00071
00072
00073
00074
00075
00077 void init_possib(){
00078 int i,j;
00079 short si;
00080 _pow = new int[_size+1];
00081 _pow[0] = 1;
00082 for (si=0; si<_size; si++){
00083 _pow[si+1] = 2*_pow[si];
00084 }
00085 _nbposs = _pow[_size-1];
00086
00087 _possib = new bool*[_nbposs];
00088 for (i=0; i<_nbposs; i++)
00089 _possib[i] = new bool[_size];
00090
00091 int pow1 = 1, pow2=_nbposs/2;
00092 for (i=0; i<_nbposs; i++)
00093 _possib[i][0] = false;
00094 for (si=1; si<_size; si++){
00095 for (i=0; i<pow1; i++)
00096 for (j=0; j<pow2; j++){
00097 _possib[(2*i+1)*pow2+j][si] = false;
00098 _possib[2*i*pow2+j][si] = true;
00099 }
00100 pow1 *= 2;
00101 pow2 /= 2;
00102 }
00103
00104
00105
00106
00107
00108
00109
00110 }
00111
00112
00114 void delete_possib(){
00115 int i;
00116 for (i=0; i<_nbposs; i++){
00117 delete [] _possib[i];
00118 }
00119 delete [] _possib;
00120 }
00121
00122 long approx_cardinal(){
00123 int maxIter = 30;
00124 double epsilon = 0.0001, test = 1., kpuiss, sum = 0, sumold;
00125 double i = 1, kfact = 1;
00126 while ((i<maxIter)&&(abs(test)>epsilon))
00127 {
00128 sumold = sum;
00129 kpuiss = pow(double(i), double(_size));
00130 kfact = kfact*i;
00131 sum = sum+kpuiss/kfact;
00132 test = sumold-sum;
00133 i++;
00134 }
00135 return ( long(sum*(exp(-1.))) +1);
00136 }
00137
00139 void cutoff_r( vector<short> & vec,
00140 short nbmaxfalse, short numfalse,
00141 short notaffected ){
00142 int i, j;
00143 short snif, newnbfalse=0;
00144
00145 if (notaffected==0){
00146
00147
00148 this->processing( numfalse, vec );
00149
00150
00151
00152
00153
00154
00155
00156
00157
00158 _cardinal++;
00159 }
00160 else{
00161
00162 int jump = _pow[_size-notaffected];
00163
00164 for ( i=0; i<_nbposs; i+=jump ){
00165
00166
00167
00168
00169
00170
00171
00172 snif = 0;
00173 newnbfalse = 0;
00174
00175 for ( j=0; j<_size; j++ ){
00176
00177 if ( vec[j]==0 ){
00178
00179 if ( _possib[i][snif++] == false ){
00180 vec[j] = numfalse;
00181 newnbfalse++;
00182 }
00183 }
00184 }
00185
00186 cutoff_r( vec,
00187 newnbfalse, numfalse+1,
00188 notaffected-newnbfalse );
00189
00190 for ( j=0; j<_size; j++ )
00191 if ( vec[j] == numfalse )
00192 vec[j] = 0;
00193 }
00194 }
00195 }
00196
00198 virtual void processing( short numfalse,
00199 const vector<short> & vec ) = 0;
00200
00201 public :
00202
00204 Partition_box( ){
00205 _size = 0;
00206 _currpart = 0;
00207 _cardinal = 0;
00208 _pow = NULL;
00209 _nbposs = 0;
00210 _possib = NULL;
00211 }
00212
00214 Partition_box( short size_ensemble ){
00215 _size = size_ensemble;
00216 _currpart = 0;
00217 if (size_ensemble<14){
00218 long card = approx_cardinal();
00219
00220
00221
00222
00223
00224
00225
00226
00227
00228 _partition.reserve( card );
00229 }
00230 _cardinal = 0;
00231 _pow = NULL;
00232 _nbpartition_with_nbelement.assign(_size,0);
00233 }
00234
00236 Partition_box( const Partition_box & p ){
00237 _size = p._size;
00238 _currpart = p._currpart;
00239 _partition.reserve = p._partition;
00240 _cardinal = p._cardinal;
00241 _pow = NULL;
00242 }
00243
00245 virtual ~Partition_box(){
00246 if (_pow)
00247 delete [] _pow;
00248 };
00249
00251 void cutoff(){
00252 vector<short> v(_size, 0);
00253 this->init_possib();
00254 _cardinal = 0;
00255 cutoff_r(v, _size, 1, _size);
00256 this->delete_possib();
00257 }
00258
00260 long tell_cardinal() const{
00261 return _cardinal;
00262 }
00263
00265 long tell_size() const{
00266 return _size;
00267 }
00268
00270 const Tpart & element( int i) const{
00271 return _partition[i];
00272 }
00273
00275 const vector< int >& nbpartition_with_nbelement() const{
00276 return _nbpartition_with_nbelement;
00277 }
00278
00280 const vector< int >& compute_nbpartition_with_nbelement(){
00281 int i, s= _partition.size();
00282 _nbpartition_with_nbelement.clear();
00283 _nbpartition_with_nbelement.assign(_size,0);
00284 for (i=0; i<s; i++)
00285 _nbpartition_with_nbelement[ _partition[i].size()-1 ]++;
00286 return _nbpartition_with_nbelement;
00287 }
00288
00289
00290 class const_iterator{
00291 private :
00292 const Partition_box<Tpart> * _part_box;
00293 long _currpart;
00294 protected :
00295 friend class Partition_box;
00296 const_iterator( const Partition_box<Tpart> & p, long currpart ){
00297 _part_box = &p;
00298 _currpart = currpart;
00299 if (p._cardinal == 0)
00300 cerr<<" cutoff required !"<<endl;
00301 }
00302 public :
00303 const_iterator( ){
00304 _currpart = -1;
00305 _part_box = NULL;
00306 }
00308 bool operator ++ () {
00309
00310 if ( _currpart<_part_box->_cardinal-1 ){
00311 _currpart++;
00312 return true;
00313 }
00314 else{
00315 _currpart++;
00316 return false;
00317 }
00318 }
00320 bool operator ++ (int) {
00321
00322 if ( _currpart<_part_box->_cardinal-1 ){
00323 _currpart++;
00324 return true;
00325 }
00326 else{
00327 _currpart++;
00328 return false;
00329 }
00330 }
00332 bool operator != ( const const_iterator & p ) const{
00333 return ( (p._part_box !=_part_box)
00334 || (p._currpart !=_currpart) );
00335 }
00337 bool operator == ( const const_iterator & p ) const{
00338 return ( (p._part_box ==_part_box)
00339 && (p._currpart ==_currpart) );
00340 }
00342 const Tpart& operator * () const{
00343 return _part_box->_partition[_currpart];
00344 }
00345
00346 const_iterator operator = ( const const_iterator & p ){
00347 if ( p != *this ){
00348 _part_box = p._part_box;
00349 _currpart = p._currpart;
00350 }
00351 return *this;
00352 }
00353 };
00354
00356 const_iterator begin() const{
00357 return const_iterator( *this, 0 );
00358 }
00360 const_iterator end() const{
00361 return const_iterator( *this, _cardinal );
00362 }
00363
00364 };
00365
00366
00367 #endif //PARTITION_BOX_H