CMS 3D CMS Logo

CombinationGenerator< T > Class Template Reference

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

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

List of all members.

Public Types

typedef vector< T > Collection
typedef vector< Collection > Combination
typedef vector< Combination > VectorOfCombinations

Public Member Functions

vector< Combination > combinations (const Collection &data) const
 Create all combinations of elements from 'data'.
vector< Combination > combinations (const Collection &data, const PartitionGenerator::Partition &partition) const
 Create all combinations obtained by dividing 'data' according to Partition 'partition'.
vector< Combination > combinations (const Collection &data, int numberOfCollections) const
 Create combinations obtained by dividing 'data' according to all partitions with 'numberOfCollections' collections.

Private Member Functions

vector< Combination > separateOneElement (const Collection &data) const
 Create all combinations obtained by dividing 'data' in two collections, the second one having only one element.
VectorOfCombinations splitInTwoCollections (const Collection &data, int sizeFirst) const
 Create all combinations obtained by dividing 'data' in two collections, the first one being of size 'sizeFirst'.

Detailed Description

template<class T>
class CombinationGenerator< 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 21 of file CombinationGenerator.h.

Member Typedef Documentation

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

Definition at line 25 of file CombinationGenerator.h.

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

Definition at line 27 of file CombinationGenerator.h.

template<class T>
typedef vector<Combination> CombinationGenerator< T >::VectorOfCombinations

Definition at line 28 of file CombinationGenerator.h.

Member Function Documentation

template<class T>
vector<Combination> CombinationGenerator< T >::combinations ( const Collection &  data  )  const [inline]

Create all combinations of elements from 'data'.

Definition at line 165 of file CombinationGenerator.h.

References CombinationGenerator< T >::combinations(), PartitionGenerator::partitions(), and python::multivaluedict::sort().

00166   {
00167 
00168     vector<Combination> combinations;
00169     Collection sorted = data;
00170     // Sort if needed
00171     if (prev_permutation(sorted.begin(), sorted.end())) {
00172       sort(sorted.begin(), sorted.end());
00173     }
00174 
00175     PartitionGenerator aPartitionGenerator;
00176     vector<PartitionGenerator::Partition> partitions 
00177       = aPartitionGenerator.partitions(data.size());
00178     
00179     for (vector<PartitionGenerator::Partition>::const_iterator idiv 
00180            = partitions.begin(); idiv != partitions.end(); idiv++) {
00181       const PartitionGenerator::Partition& partition = *idiv;
00182 
00183       vector<Combination> subCombinations 
00184         = this->combinations(data, partition);
00185       for ( typename vector<Combination>::const_iterator iComb 
00186              = subCombinations.begin(); 
00187            iComb != subCombinations.end(); iComb++) {
00188         combinations.push_back(*iComb);
00189       }
00190     }
00191     return combinations;
00192   }

template<class T>
vector<Combination> CombinationGenerator< T >::combinations ( const Collection &  data,
const PartitionGenerator::Partition &  partition 
) const [inline]

Create all combinations obtained by dividing 'data' according to Partition 'partition'.

Definition at line 71 of file CombinationGenerator.h.

References bookConverter::comb, CombinationGenerator< T >::combinations(), it, k, size, python::multivaluedict::sort(), and CombinationGenerator< T >::splitInTwoCollections().

00073   {
00074 
00075     vector<Combination> combinations;
00076 
00077     // Check that sum of collection sizes in 'partition' 
00078     // amounts to number of elements in 'data' 
00079     int nElts = 0;
00080     for (PartitionGenerator::Partition::const_iterator iSize 
00081            = partition.begin(); iSize != partition.end(); iSize++) {
00082       nElts += *iSize;
00083     }
00084     if (nElts != data.size()) return combinations;
00085 
00086     Collection sortedData = data;
00087     // Sort if needed
00088     if (prev_permutation(sortedData.begin(), sortedData.end())) {
00089       sort(sortedData.begin(), sortedData.end());
00090     }
00091 
00092     // Create initial combination and put it on the stack
00093     Combination comb;
00094     comb.push_back(sortedData);
00095     if (partition.size() == 1) {
00096       // Return only one combination with only one collection
00097       combinations.push_back(comb);
00098       return combinations;
00099     }
00100     stack<Combination> cStack;
00101     cStack.push(comb);
00102 
00103     // Sort partitions by size 
00104     // Let 'sortedPartition' = ( n0, n1,... nk, nk+1,... nm ) 
00105     // Ordering is >= to speed up partitioning: n0 >= n1 >=... >= nm 
00106     PartitionGenerator::Partition sortedPartition = partition;
00107     sort(sortedPartition.begin(), sortedPartition.end(), greater_equal<int>());
00108 
00109     while (!cStack.empty()) {
00110 
00111       // 'combination' popped out of the stack 
00112       Combination combination = cStack.top(); cStack.pop();
00113 
00114       // At this stage 'combination' is made of collections 
00115       // of sizes ( n0+n1+...+nk, nk+1,... nm ) 
00116       // Now generate all combinations obtained by splitting 
00117       // the first collection of 'combination' in two, 
00118       // according to Partition 'biPartition' = (n0+n1+...+nk-1, nk) 
00119       int k = sortedPartition.size() - combination.size();
00120       int size = 0;
00121       for (int iColl = 0; iColl != k; iColl++) {
00122         size += sortedPartition[iColl];
00123       }
00124       PartitionGenerator::Partition biPartition(2);
00125       biPartition[0] = size; 
00126       biPartition[1] = sortedPartition[k];
00127 
00128       VectorOfCombinations subCombinations 
00129         = splitInTwoCollections(combination[0], biPartition[0]);
00130       for (typename vector<Combination>::const_iterator iComb = subCombinations.begin();
00131            iComb != subCombinations.end(); iComb++) { 
00132 
00133         // Check ordering of successive bins of equal size 
00134         if (combination.size() > 1) {
00135           if ((*iComb)[1].size() == combination[1].size()) {
00136             Collection adjBins;
00137             adjBins.push_back((*iComb)[1][0]);
00138             adjBins.push_back(combination[1][0]);
00139             // Drop 'combination' if successive bins of equal size not ordered 
00140             // i.e. if previous permutation exists 
00141             if (prev_permutation(adjBins.begin(), adjBins.end())) continue;
00142           }
00143         }
00144 
00145         // Append remaining collections of 'combination'
00146         Combination merged = *iComb;
00147         typename Combination::const_iterator it = combination.begin(); it++;
00148         for ( ; it != combination.end(); it++) { merged.push_back(*it); }
00149 
00150         // Store combination 'merged' if partitioning is complete, 
00151         // otherwise put it on the stack for further partitioning. 
00152         if (merged.size() == sortedPartition.size()) {
00153           combinations.push_back(merged);
00154         } else {
00155           cStack.push(merged);
00156         }
00157       }
00158     }
00159     return combinations;
00160   }

template<class T>
vector<Combination> CombinationGenerator< T >::combinations ( const Collection &  data,
int  numberOfCollections 
) const [inline]

Create combinations obtained by dividing 'data' according to all partitions with 'numberOfCollections' collections.

Definition at line 34 of file CombinationGenerator.h.

References begin, python::multivaluedict::sort(), and PartitionGenerator::sortedPartitions().

Referenced by CombinationGenerator< T >::combinations(), CombinationGenerator< T >::separateOneElement(), and CombinationGenerator< T >::splitInTwoCollections().

00035   {
00036     vector<Combination> combinations;
00037     Collection sorted = data;
00038 
00039     // Sort if needed
00040     if (prev_permutation(sorted.begin(), sorted.end())) {
00041       sort(sorted.begin(), sorted.end());
00042     }
00043 
00044     // Create sorted partitions
00045     PartitionGenerator aPartitionGenerator;
00046     vector< vector<PartitionGenerator::Partition> > partitions 
00047       = aPartitionGenerator.sortedPartitions(data.size());
00048     
00049     // Use partitions of size 'numberOfCollections' only
00050     for (vector<PartitionGenerator::Partition>::const_iterator idiv 
00051            = partitions[numberOfCollections-1].begin(); 
00052          idiv != partitions[numberOfCollections-1].end(); idiv++) {
00053 
00054       const PartitionGenerator::Partition& partition = *idiv;
00055       vector<Combination> subCombinations 
00056         = this->combinations(data, partition);
00057       for ( typename vector<Combination>::const_iterator iComb 
00058              = subCombinations.begin(); 
00059            iComb != subCombinations.end(); iComb++) {
00060         combinations.push_back(*iComb);
00061       }
00062     }
00063     return combinations;
00064   }

template<class T>
vector<Combination> CombinationGenerator< T >::separateOneElement ( const Collection &  data  )  const [inline, private]

Create all combinations obtained by dividing 'data' in two collections, the second one having only one element.

Definition at line 255 of file CombinationGenerator.h.

References coll, bookConverter::comb, CombinationGenerator< T >::combinations(), i, and j.

Referenced by CombinationGenerator< T >::splitInTwoCollections().

00256   {
00257     vector<Combination> combinations;
00258     for ( typename Collection::const_iterator i = data.begin(); i != data.end(); i++) {
00259       Combination comb;
00260       Collection single; single.push_back(*i);
00261       Collection coll; 
00262       typename Collection::const_iterator j = data.begin();
00263       for ( ; j != i; j++) { coll.push_back(*j); }
00264       j++;
00265       for ( ; j != data.end(); j++) { coll.push_back(*j); }
00266       comb.push_back(coll); comb.push_back(single);
00267       combinations.push_back(comb);
00268     }
00269     return combinations;
00270   }

template<class T>
VectorOfCombinations CombinationGenerator< T >::splitInTwoCollections ( const Collection &  data,
int  sizeFirst 
) const [inline, private]

Create all combinations obtained by dividing 'data' in two collections, the first one being of size 'sizeFirst'.

Definition at line 200 of file CombinationGenerator.h.

References collection, bookConverter::comb, CombinationGenerator< T >::combinations(), edm::second(), CombinationGenerator< T >::separateOneElement(), and size.

Referenced by CombinationGenerator< T >::combinations().

00202   {
00203     vector<Combination> combinations;
00204     stack<Combination> cStack;
00205 
00206     // Create first combination with 2 partitions
00207     Combination comb; comb.push_back(data); comb.push_back(Collection());
00208     cStack.push(comb);
00209 
00210     while (!cStack.empty()) {
00211       Combination combination = cStack.top();
00212       cStack.pop();
00213 
00214       Collection collection = combination[0];
00215       vector<Combination> subCombinations = separateOneElement(collection);
00216       
00217       for ( typename vector<Combination>::const_iterator iComb = subCombinations.begin();
00218            iComb != subCombinations.end(); iComb++) {
00219 
00220         Collection second = combination[1];
00221         second.push_back((*iComb)[1][0]);
00222 
00223         // Abandon current combination if not ordered, 
00224         // i.e. if previous permutation exists 
00225         bool ordered = !prev_permutation(second.begin(), second.end());
00226         if (!ordered) continue;
00227         next_permutation(second.begin(), second.end());
00228 
00229         if ((*iComb)[0].size() == second.size()) {
00230           Collection adjBins;
00231           adjBins.push_back((*iComb)[0][0]);
00232           adjBins.push_back(second[0]);
00233           // Abandon current combination if successive bins of equal size 
00234           // not ordered, i.e. if previous permutation exists 
00235           if (prev_permutation(adjBins.begin(), adjBins.end())) continue;
00236         }
00237 
00238         Combination stored; 
00239         stored.push_back((*iComb)[0]);
00240         stored.push_back(second);
00241 
00242         if (stored[0].size() == sizeFirst) {
00243           combinations.push_back(stored);
00244         } else {
00245           cStack.push(stored);
00246         }
00247       }
00248     }
00249     return combinations;
00250   }

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