CMS 3D CMS Logo

SequentialCombinationGenerator< T > Class Template Reference

Class to compute all distinct Combinations of a collection 'data' of objects of type 'T'. More...

#include <CommonTools/Statistics/interface/SequentialCombinationGenerator.h>

List of all members.

Public Types

typedef vector< T > Collection
typedef vector< Collection > Combination
typedef
SequentialPartitionGenerator::Partition 		Partition
typedef vector< int > Vecint

Public Member Functions

Combination next_combination (Collection &coll)
 Create combinations obtained by dividing 'coll' according to partition the_part defined by the constructor.
 SequentialCombinationGenerator (Partition &part)

Private Member Functions

Vecint next_combi (Vecint &cold, int n, const Partition &p)
Vecint next_subset (Vecint g, Vecint c)
void vecprint (const Vecint &v) const

Private Attributes

bool dbg
Vecint the_comb
int the_k
int the_n
Partition the_part

Detailed Description

template<class T>
class SequentialCombinationGenerator< T >

Class to compute all distinct Combinations of a collection 'data' of objects of type 'T'.

A Combination is a set of collections, each collection containing one or more objects, with any object in 'data' assigned to exactly one collection.

Definition at line 23 of file SequentialCombinationGenerator.h.

Member Typedef Documentation

template<class T>
typedef vector<T> SequentialCombinationGenerator< T >::Collection

Definition at line 26 of file SequentialCombinationGenerator.h.

template<class T>
typedef vector<Collection> SequentialCombinationGenerator< T >::Combination

Definition at line 27 of file SequentialCombinationGenerator.h.

template<class T>
typedef SequentialPartitionGenerator::Partition SequentialCombinationGenerator< T >::Partition

Definition at line 25 of file SequentialCombinationGenerator.h.

template<class T>
typedef vector<int> SequentialCombinationGenerator< T >::Vecint

Definition at line 28 of file SequentialCombinationGenerator.h.

Constructor & Destructor Documentation

template<class T>
SequentialCombinationGenerator< T >::SequentialCombinationGenerator ( Partition &  part  )  [inline]

Definition at line 30 of file SequentialCombinationGenerator.h.

References python::multivaluedict::sort(), SequentialCombinationGenerator< T >::the_comb, SequentialCombinationGenerator< T >::the_n, and SequentialCombinationGenerator< T >::the_part.

00030                                                       :
00031       the_part ( part ), the_k ( part.size() ),
00032       the_n ( accumulate ( part.begin(), part.end(), 0 ) )
00033   {
00034     sort(the_part.begin(),the_part.end());
00035     the_comb.reserve(the_n);
00036   };

Member Function Documentation

template<class T>
Vecint SequentialCombinationGenerator< T >::next_combi ( Vecint &  cold,
int  n,
const Partition &  p 
) [inline, private]

Definition at line 66 of file SequentialCombinationGenerator.h.

References edmNew::copy(), empty, i, j, k, SequentialCombinationGenerator< T >::next_subset(), p1, s, python::multivaluedict::sort(), and ss.

Referenced by SequentialCombinationGenerator< T >::next_combination().

00067   {
00068     Vecint empty;
00069     if (cold.size()==0) { // first entry, initialize
00070       cold.reserve(n);
00071       for (int i=0;i<n;cold.push_back(++i));
00072       return cold;
00073     }
00074     int k=p.size();
00075     if (k==1) return empty;
00076     Vecint cnew(cold);
00077     int n1=n-p[0];
00078     Vecint cold1(cold.begin()+p[0],cold.end());
00079     Vecint cnew1(n1);
00080     Partition p1(p.begin()+1,p.end());
00081     cnew1=next_combi(cold1,n1,p1);
00082     if (cnew1.size()!=0) {
00083       copy(cnew1.begin(),cnew1.end(),cnew.begin()+p[0]);
00084       return cnew;
00085     }
00086     Vecint cold2(cold.begin(),cold.begin()+p[0]);
00087     Vecint cnew2(p[0]);
00088     sort(cold.begin(),cold.end());
00089     sort(cold2.begin(),cold2.end());
00090     cnew2=next_subset(cold,cold2);
00091     if (cnew2.size()==0) return empty;
00092     copy(cnew2.begin(),cnew2.begin()+p[0],cnew.begin());
00093     Vecint ss(n1);
00094     set_difference(cold.begin(),cold.end(),
00095                    cnew2.begin(),cnew2.end(),ss.begin());
00096     int ip=p[0];
00097     for (int i=1;i<k;i++) {
00098       if (p[i]!=p[i-1]) {
00099         copy(ss.begin(),ss.end(),&cnew[ip]);
00100         return cnew;
00101       }
00102       int mincnew2=cnew2[0];
00103       if (ss[n1-1]<mincnew2) return empty;
00104       Vecint::iterator j1=find_if(ss.begin(),ss.end(),bind2nd(greater<int>(),mincnew2));
00105       if (ss.end()-j1 < p[i]) return empty;
00106       Vecint sss(j1,ss.end());
00107       for (int j=0;j<p[i];cnew[ip+j]=cnew2[j]=sss[j++]);
00108       int n2=ss.size()-cnew2.size();
00109       if (n2==0) return cnew;
00110       Vecint s(n2);
00111       set_difference(ss.begin(),ss.end(),cnew2.begin(),cnew2.end(),s.begin());
00112       ss=s;
00113       ip+=p[i];
00114     }
00115    
00116    return empty; 
00117  
00118   };

template<class T>
Combination SequentialCombinationGenerator< T >::next_combination ( Collection &  coll  )  [inline]

Create combinations obtained by dividing 'coll' according to partition the_part defined by the constructor.

Definition at line 41 of file SequentialCombinationGenerator.h.

References bookConverter::comb, SequentialCombinationGenerator< T >::dbg, empty, i, j, edm::es::l(), SequentialCombinationGenerator< T >::next_combi(), pyDBSRunClass::temp, SequentialCombinationGenerator< T >::the_comb, SequentialCombinationGenerator< T >::the_k, SequentialCombinationGenerator< T >::the_n, and SequentialCombinationGenerator< T >::the_part.

00042   {
00043     dbg=false;
00044     Combination comb;
00045     Vecint newcomb=next_combi(the_comb,the_n,the_part);
00046     the_comb=newcomb;
00047     if (newcomb.size()==0) {
00048       Combination empty;
00049       return empty;
00050     }
00051     int i=0;
00052     for (int j=0;j<the_k;j++) 
00053     {
00054       Collection temp;
00055       for (int l=0;l<the_part[j];l++) 
00056       {
00057         temp.push_back(coll[the_comb[i]-1]);
00058         i++;
00059       }
00060       comb.push_back(temp);
00061     }
00062     return comb;
00063   };

template<class T>
Vecint SequentialCombinationGenerator< T >::next_subset ( Vecint  g,
Vecint  c 
) [inline, private]

Definition at line 120 of file SequentialCombinationGenerator.h.

References edmNew::copy(), empty, find(), g2, i, k, and n.

Referenced by SequentialCombinationGenerator< T >::next_combi().

00121   {
00122     Vecint empty;
00123     int n=g.size();
00124     int k=c.size();
00125     typename Vecint::iterator ind;
00126     for (int i=k-1;i>=0;i--) {
00127       if (c[i]<g[n-k+i]) {
00128         
00129         
00130 //      ind=find(&g[0],&g[n-k+i],c[i])+1;
00131         
00132         Vecint::iterator g2 = g.begin();
00133         advance(g2,n-k+i);  
00134         
00135         ind=find(g.begin(),g2,c[i]);
00136         
00137         ind++;
00138         
00139         
00140         
00141         copy(ind,ind+k-i,&c[i]);
00142         return c;
00143       }
00144     }
00145     return empty;
00146   };

template<class T>
void SequentialCombinationGenerator< T >::vecprint ( const Vecint &  v  )  const [inline, private]

Definition at line 148 of file SequentialCombinationGenerator.h.

References GenMuonPlsPt100GeV_cfg::cout, lat::endl(), i, and n.

00149   {
00150     int n=v.size();
00151     for (int i=0;i<n;cout << v[i++]);
00152     cout << endl;
00153   };

Member Data Documentation

template<class T>
bool SequentialCombinationGenerator< T >::dbg [mutable, private]

Definition at line 160 of file SequentialCombinationGenerator.h.

Referenced by SequentialCombinationGenerator< T >::next_combination().

template<class T>
Vecint SequentialCombinationGenerator< T >::the_comb [mutable, private]

Definition at line 159 of file SequentialCombinationGenerator.h.

Referenced by SequentialCombinationGenerator< T >::next_combination(), and SequentialCombinationGenerator< T >::SequentialCombinationGenerator().

template<class T>
int SequentialCombinationGenerator< T >::the_k [private]

Definition at line 157 of file SequentialCombinationGenerator.h.

Referenced by SequentialCombinationGenerator< T >::next_combination().

template<class T>
int SequentialCombinationGenerator< T >::the_n [private]

Definition at line 153 of file SequentialCombinationGenerator.h.

Referenced by SequentialCombinationGenerator< T >::next_combination(), and SequentialCombinationGenerator< T >::SequentialCombinationGenerator().

template<class T>
Partition SequentialCombinationGenerator< T >::the_part [private]

Definition at line 158 of file SequentialCombinationGenerator.h.

Referenced by SequentialCombinationGenerator< T >::next_combination(), and SequentialCombinationGenerator< T >::SequentialCombinationGenerator().

The documentation for this class was generated from the following file:
Generated on Tue Jun 9 18:31:31 2009 for CMSSW by  doxygen 1.5.4