CMS 3D CMS Logo

Combinatorics Class Reference

#include <HeavyFlavorAnalysis/Skimming/interface/Combinatorics.h>

List of all members.

Public Member Functions

 Combinatorics (Int_t Set, Int_t Subset)
Int_t EqualPermutation (std::vector< UInt_t > permutation1, std::vector< UInt_t > permutation2)
Int_t EqualPermutation_2_0 (std::vector< UInt_t > permutation1, std::vector< UInt_t > permutation2)
Int_t EqualPermutation_2_2 (std::vector< UInt_t > permutation1, std::vector< UInt_t > permutation2)
Int_t EqualPermutation_N_1 (std::vector< UInt_t > permutation1, std::vector< UInt_t > permutation2)
std::vector< std::vector
< UInt_t > > 		GetCombinations ()
std::vector< std::vector
< UInt_t > > 		GetCombinations_2_0 ()
std::vector< std::vector
< UInt_t > > 		GetCombinations_2_2 ()
std::vector< std::vector
< UInt_t > > 		GetCombinations_N_1 ()
std::vector< std::vector
< UInt_t > > 		GetPermutations ()
void Print (std::vector< std::vector< UInt_t > > permutations)
void Print (std::vector< UInt_t > permutation)
virtual ~Combinatorics ()

Private Member Functions

Int_t CalculatePermutations ()
void initial_permutation (int size, int *permutation)
void initial_subset (int k, int *subset)
Bool_t next_permutation (int size, int *permutation)
Bool_t next_subset (int n, int k, int *subset)
std::vector< UInt_t > Rotate (std::vector< UInt_t > permutation, UInt_t digits)
void Skip_2_0 (std::vector< std::vector< UInt_t > > permutation1, std::vector< std::vector< UInt_t > > &permutation2)
void Skip_2_2 (std::vector< std::vector< UInt_t > > permutation1, std::vector< std::vector< UInt_t > > &permutation2)

Private Attributes

std::vector< std::vector
< UInt_t > > 		m_Combinations
std::vector< std::vector
< UInt_t > > 		m_Permutations
const Int_t m_SetQuantity
std::vector< UInt_t > m_Subset
const Int_t m_SubsetQuantity

Detailed Description

Definition at line 17 of file Combinatorics.h.

Constructor & Destructor Documentation

Combinatorics::Combinatorics ( Int_t  Set,
Int_t  Subset 
)

Definition at line 19 of file Combinatorics.cc.

References CalculatePermutations().

00019                                                                     :
00020 
00021   m_SetQuantity(SetQuantity),
00022   m_SubsetQuantity(SubsetQuantity)
00023 {
00024   // Get permutations
00025   CalculatePermutations();
00026 }

Combinatorics::~Combinatorics (  )  [virtual]

Definition at line 32 of file Combinatorics.cc.

00033 {}

Member Function Documentation

Int_t Combinatorics::CalculatePermutations (  )  [private]

Definition at line 47 of file Combinatorics.cc.

References lat::endl(), i, initial_permutation(), initial_subset(), m_Permutations, m_SetQuantity, m_Subset, m_SubsetQuantity, next_permutation(), and next_subset().

Referenced by Combinatorics().

00048 {
00049   if (m_SetQuantity < 1 || m_SubsetQuantity < 1 || (m_SetQuantity < m_SubsetQuantity)) 
00050     {
00051       edm::LogWarning("Combinatorics") << "[Combinatorics] No valid choice of set or subset!" << endl;
00052       return -1;
00053     }
00054   
00055   Int_t* currentSubset = new Int_t[m_SubsetQuantity];
00056   Int_t* currentMapping = new Int_t[m_SetQuantity];
00057 
00058   initial_subset(m_SubsetQuantity, currentSubset);    
00059   do
00060     {
00061       initial_permutation(m_SetQuantity, currentMapping);        
00062       do
00063         {
00064           for (UShort_t i = 0; i < m_SubsetQuantity; i++) 
00065             {
00066               m_Subset.push_back(currentSubset[currentMapping[i]]);
00067             }
00068           m_Permutations.push_back(m_Subset);
00069           m_Subset.clear();
00070         }
00071       while (next_permutation(m_SubsetQuantity, currentMapping));
00072     }
00073   while (next_subset(m_SetQuantity, m_SubsetQuantity, currentSubset));
00074 
00075   delete[] currentSubset;
00076   delete[] currentMapping;
00077 
00078   return 0;
00079 }

Int_t Combinatorics::EqualPermutation ( std::vector< UInt_t >  permutation1,
std::vector< UInt_t >  permutation2 
)

Referenced by GetCombinations().

Int_t Combinatorics::EqualPermutation_2_0 ( std::vector< UInt_t >  permutation1,
std::vector< UInt_t >  permutation2 
)

Int_t Combinatorics::EqualPermutation_2_2 ( std::vector< UInt_t >  permutation1,
std::vector< UInt_t >  permutation2 
)

Int_t Combinatorics::EqualPermutation_N_1 ( std::vector< UInt_t >  permutation1,
std::vector< UInt_t >  permutation2 
)

vector< vector< UInt_t > > Combinatorics::GetCombinations (  ) 

Definition at line 189 of file Combinatorics.cc.

References lat::endl(), EqualPermutation(), i, LogDebug, m_Combinations, and m_Permutations.

Referenced by GetCombinations_N_1().

00190 {
00191   if (m_Permutations.size() == 0) 
00192     {
00193       LogDebug("Combinatorics") << "Nothing to do." << endl;
00194       return m_Combinations;
00195     }
00196   
00197   m_Combinations.push_back(m_Permutations.at(0));
00198 
00199   for (UInt_t i = 1; i < m_Permutations.size(); i++)
00200     {
00201       if (!EqualPermutation(m_Combinations.back(), m_Permutations.at(i))) 
00202         {
00203           m_Combinations.push_back(m_Permutations.at(i));
00204         }
00205     }
00206   return m_Combinations;
00207 }

vector< vector< UInt_t > > Combinatorics::GetCombinations_2_0 (  ) 

Definition at line 270 of file Combinatorics.cc.

References lat::endl(), LogDebug, m_Permutations, m_SubsetQuantity, and Skip_2_0().

00271 {
00272   // combination vector returned
00273   vector< vector <UInt_t> > FinalCombinations; 
00274 
00275   if (m_Permutations.size() == 0) 
00276     {
00277       LogDebug("Combinatorics") << "[Combinatorics::GetCombinations_2_0] Nothing to do." << endl;
00278       return FinalCombinations;
00279     }
00280   
00281   // So far only for subsets of four indices
00282   if (m_SubsetQuantity != 4) 
00283     {
00284       edm::LogWarning("Combinatorics") << "[Combinatorics::GetCombinations_2_0] Subset must be 4." << endl;
00285       return FinalCombinations;
00286     }
00287 
00288   // Skip specific permutations
00289   Skip_2_0(m_Permutations, FinalCombinations);
00290 
00291   return FinalCombinations;
00292 }

vector< vector< UInt_t > > Combinatorics::GetCombinations_2_2 (  ) 

Definition at line 239 of file Combinatorics.cc.

References lat::endl(), LogDebug, m_Permutations, m_SubsetQuantity, and Skip_2_2().

00240 {
00241   // combination vector returned
00242   vector< vector <UInt_t> > FinalCombinations; 
00243 
00244   if (m_Permutations.size() == 0) 
00245     {
00246       LogDebug("Combinatorics") << "[Combinatorics::GetCombinations_2_2] Nothing to do." << endl;
00247       return FinalCombinations;
00248     }
00249   
00250   // So far only for subsets of four indices
00251   if (m_SubsetQuantity != 4) 
00252     {
00253       edm::LogWarning("Combinatorics") << "[Combinatorics::GetCombinations_2_2] Subset must be 4." << endl;
00254       return FinalCombinations;
00255     }
00256 
00257   // Skip specific permutations
00258   Skip_2_2(m_Permutations, FinalCombinations);
00259 
00260   return FinalCombinations;
00261 }

vector< vector< UInt_t > > Combinatorics::GetCombinations_N_1 (  ) 

Definition at line 416 of file Combinatorics.cc.

References lat::endl(), GetCombinations(), i, j, LogDebug, m_Combinations, and Rotate().

00417 {
00418   // Get combinations 
00419   m_Combinations.clear();
00420   GetCombinations();
00421   
00422   // combination vector returned
00423   vector < vector <UInt_t> > FinalCombinations;
00424 
00425   if (m_Combinations.size() == 0) 
00426     {
00427       LogDebug("Combinatorics") << "[Combinatorics::GetCombinationsThreeByOne] Nothing to do." << endl;
00428       return FinalCombinations;
00429     }
00430   
00431   for (UInt_t i = 0; i < m_Combinations.size(); i++)
00432     {
00433       vector <UInt_t> RotatingPermutation = m_Combinations.at(i);
00434       FinalCombinations.push_back(m_Combinations.at(i));
00435 
00436       for (UInt_t j = 1; j < RotatingPermutation.size(); j++)
00437         {
00438           FinalCombinations.push_back(Rotate(RotatingPermutation,j));
00439         }
00440     }
00441   return FinalCombinations;
00442 }

vector< vector< UInt_t > > Combinatorics::GetPermutations (  ) 

Definition at line 39 of file Combinatorics.cc.

References m_Permutations.

00040 {
00041   return m_Permutations;
00042 }

void Combinatorics::initial_permutation ( int  size,
int *  permutation 
) [private]

Definition at line 85 of file Combinatorics.cc.

References i.

Referenced by CalculatePermutations().

00086 {
00087   for (int i = 0; i < size; i++) 
00088     {
00089       permutation[i] = i;
00090     }
00091 }

void Combinatorics::initial_subset ( int  k,
int *  subset 
) [private]

Definition at line 97 of file Combinatorics.cc.

References i.

Referenced by CalculatePermutations().

00098 {
00099   for (int i = 0; i < k; i++) 
00100     {
00101       subset[i] = i;
00102     }
00103 }

Bool_t Combinatorics::next_permutation ( int  size,
int *  permutation 
) [private]

Definition at line 109 of file Combinatorics.cc.

References i, j, k, and tmp.

Referenced by CalculatePermutations().

00110 {
00111   int i, j, k;
00112   if (size < 2) return false;
00113   i = size - 2;
00114   
00115   while ((permutation[i] > permutation[i+1]) && (i != 0)) 
00116     {
00117       i--;
00118     }
00119   if ((i == 0) && (permutation[0] > permutation[1])) return false;
00120   
00121   k = i + 1;
00122   for (j = i + 2; j < size; j++ ) 
00123     {
00124       if ((permutation[j] > permutation[i]) && (permutation[j] < permutation[k])) 
00125         {
00126           k = j;
00127         }
00128     }
00129   
00130   // swap i and k 
00131   {
00132     int tmp = permutation[i];
00133     permutation[i] = permutation[k];
00134     permutation[k] = tmp;
00135   }
00136   
00137   for (j = i + 1; j <= ((size + i) / 2); j++) 
00138     {
00139       int tmp = permutation[j];
00140       permutation[j] = permutation[size + i - j];
00141       permutation[size + i - j] = tmp;
00142     }
00143 
00144   // return whether a next permutation exists
00145   return true;
00146 }

Bool_t Combinatorics::next_subset ( int  n,
int  k,
int *  subset 
) [private]

Definition at line 155 of file Combinatorics.cc.

References i, and j.

Referenced by CalculatePermutations().

00156 {
00157   int i;
00158   int j;
00159   int jsave;
00160   bool done;
00161   
00162   if ( subset[0] < n-k )
00163     {
00164       done = false;
00165       jsave = k-1;
00166       for ( j = 0; j < k-1; j++ )
00167         {
00168           if ( subset[j] + 1 < subset[j+1] )
00169             {
00170               jsave = j;
00171               break;
00172             }
00173         }
00174       for ( i = 0; i < jsave; i++ ) subset[i] = i;
00175       subset[jsave] = subset[jsave] + 1;
00176     }
00177   else
00178     {
00179       done = true;
00180     }
00181   // return whether a next subset exists
00182   return !done;
00183 }

void Combinatorics::Print ( std::vector< std::vector< UInt_t > >  permutations  ) 

void Combinatorics::Print ( std::vector< UInt_t >  permutation  ) 

std::vector<UInt_t> Combinatorics::Rotate ( std::vector< UInt_t >  permutation,
UInt_t  digits 
) [private]

Referenced by GetCombinations_N_1().

void Combinatorics::Skip_2_0 ( std::vector< std::vector< UInt_t > >  permutation1,
std::vector< std::vector< UInt_t > > &  permutation2 
) [private]

Referenced by GetCombinations_2_0().

void Combinatorics::Skip_2_2 ( std::vector< std::vector< UInt_t > >  permutation1,
std::vector< std::vector< UInt_t > > &  permutation2 
) [private]

Referenced by GetCombinations_2_2().

Member Data Documentation

std::vector<std::vector <UInt_t> > Combinatorics::m_Combinations [private]

Definition at line 64 of file Combinatorics.h.

Referenced by GetCombinations(), and GetCombinations_N_1().

std::vector<std::vector <UInt_t> > Combinatorics::m_Permutations [private]

Definition at line 63 of file Combinatorics.h.

Referenced by CalculatePermutations(), GetCombinations(), GetCombinations_2_0(), GetCombinations_2_2(), and GetPermutations().

const Int_t Combinatorics::m_SetQuantity [private]

Definition at line 59 of file Combinatorics.h.

Referenced by CalculatePermutations().

std::vector<UInt_t> Combinatorics::m_Subset [private]

Definition at line 62 of file Combinatorics.h.

Referenced by CalculatePermutations().

const Int_t Combinatorics::m_SubsetQuantity [private]

Definition at line 60 of file Combinatorics.h.

Referenced by CalculatePermutations(), GetCombinations_2_0(), and GetCombinations_2_2().

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