Statistics/interface/CombinationGenerator.h

0001 #ifndef _CombinationGenerator_H_
0002 #define _CombinationGenerator_H_
0003
0004 #include "CommonTools/Statistics/interface/PartitionGenerator.h"
0005 #include <vector>
0006 #include <stack>
0007 #include <algorithm>
0008 #include <functional>
0009
0010 /** Class to compute all distinct Combinations
0011  *  of a collection 'data' of objects of type 'T'.
0012  *  A Combination is a set of collections, each collection
0013  *  containing one or more objects, with any object in 'data'
0014  *  assigned to exactly one collection.
0015  */
0016
0017 template <class T>
0018 class CombinationGenerator {
0019 public:
0020   typedef std::vector<T> Collection;
0021
0022   typedef std::vector<Collection> Combination;
0023   typedef std::vector<Combination> VectorOfCombinations;
0024
0025   /** Create combinations obtained by dividing 'data'
0026    *  according to all partitions with 'numberOfCollections' collections.
0027    */
0028   std::vector<Combination> combinations(const Collection& data, int numberOfCollections) const {
0029     std::vector<Combination> combinations;
0030     Collection sorted = data;
0031
0032     // Sort if needed
0033     if (prev_permutation(sorted.begin(), sorted.end())) {
0034       sort(sorted.begin(), sorted.end());
0035     }
0036
0037     // Create sorted partitions
0038     PartitionGenerator aPartitionGenerator;
0039     std::vector<std::vector<PartitionGenerator::Partition> > partitions =
0040         aPartitionGenerator.sortedPartitions(data.size());
0041
0042     // Use partitions of size 'numberOfCollections' only
0043     for (std::vector<PartitionGenerator::Partition>::const_iterator idiv = partitions[numberOfCollections - 1].begin();
0044          idiv != partitions[numberOfCollections - 1].end();
0045          idiv++) {
0046       const PartitionGenerator::Partition& partition = *idiv;
0047       std::vector<Combination> subCombinations = this->combinations(data, partition);
0048       for (typename std::vector<Combination>::const_iterator iComb = subCombinations.begin();
0049            iComb != subCombinations.end();
0050            iComb++) {
0051         combinations.push_back(*iComb);
0052       }
0053     }
0054     return combinations;
0055   }
0056
0057   /** Create all combinations obtained by dividing 'data'
0058    *  according to Partition 'partition'.
0059    */
0060   std::vector<Combination> combinations(const Collection& data, const PartitionGenerator::Partition& partition) const {
0061     std::vector<Combination> combinations;
0062
0063     // Check that sum of collection sizes in 'partition'
0064     // amounts to number of elements in 'data'
0065     int nElts = 0;
0066     for (PartitionGenerator::Partition::const_iterator iSize = partition.begin(); iSize != partition.end(); iSize++) {
0067       nElts += *iSize;
0068     }
0069     if (nElts != data.size())
0070       return combinations;
0071
0072     Collection sortedData = data;
0073     // Sort if needed
0074     if (prev_permutation(sortedData.begin(), sortedData.end())) {
0075       sort(sortedData.begin(), sortedData.end());
0076     }
0077
0078     // Create initial combination and put it on the stack
0079     Combination comb;
0080     comb.push_back(sortedData);
0081     if (partition.size() == 1) {
0082       // Return only one combination with only one collection
0083       combinations.push_back(comb);
0084       return combinations;
0085     }
0086     std::stack<Combination> cStack;
0087     cStack.push(comb);
0088
0089     // Sort partitions by size
0090     // Let 'sortedPartition' = ( n0, n1,... nk, nk+1,... nm )
0091     // Ordering is >= to speed up partitioning: n0 >= n1 >=... >= nm
0092     PartitionGenerator::Partition sortedPartition = partition;
0093     sort(sortedPartition.begin(), sortedPartition.end(), std::greater_equal<int>());
0094
0095     while (!cStack.empty()) {
0096       // 'combination' popped out of the stack
0097       Combination combination = cStack.top();
0098       cStack.pop();
0099
0100       // At this stage 'combination' is made of collections
0101       // of sizes ( n0+n1+...+nk, nk+1,... nm )
0102       // Now generate all combinations obtained by splitting
0103       // the first collection of 'combination' in two,
0104       // according to Partition 'biPartition' = (n0+n1+...+nk-1, nk)
0105       int k = sortedPartition.size() - combination.size();
0106       int size = 0;
0107       for (int iColl = 0; iColl != k; iColl++) {
0108         size += sortedPartition[iColl];
0109       }
0110       PartitionGenerator::Partition biPartition(2);
0111       biPartition[0] = size;
0112       biPartition[1] = sortedPartition[k];
0113
0114       VectorOfCombinations subCombinations = splitInTwoCollections(combination[0], biPartition[0]);
0115       for (typename std::vector<Combination>::const_iterator iComb = subCombinations.begin();
0116            iComb != subCombinations.end();
0117            iComb++) {
0118         // Check ordering of successive bins of equal size
0119         if (combination.size() > 1) {
0120           if ((*iComb)[1].size() == combination[1].size()) {
0121             Collection adjBins;
0122             adjBins.push_back((*iComb)[1][0]);
0123             adjBins.push_back(combination[1][0]);
0124             // Drop 'combination' if successive bins of equal size not ordered
0125             // i.e. if previous permutation exists
0126             if (prev_permutation(adjBins.begin(), adjBins.end()))
0127               continue;
0128           }
0129         }
0130
0131         // Append remaining collections of 'combination'
0132         Combination merged = *iComb;
0133         typename Combination::const_iterator it = combination.begin();
0134         it++;
0135         for (; it != combination.end(); it++) {
0136           merged.push_back(*it);
0137         }
0138
0139         // Store combination 'merged' if partitioning is complete,
0140         // otherwise put it on the stack for further partitioning.
0141         if (merged.size() == sortedPartition.size()) {
0142           combinations.push_back(merged);
0143         } else {
0144           cStack.push(merged);
0145         }
0146       }
0147     }
0148     return combinations;
0149   }
0150
0151   /** Create all combinations of elements from 'data'.
0152    */
0153   std::vector<Combination> combinations(const Collection& data) const {
0154     std::vector<Combination> combinations;
0155     Collection sorted = data;
0156     // Sort if needed
0157     if (prev_permutation(sorted.begin(), sorted.end())) {
0158       sort(sorted.begin(), sorted.end());
0159     }
0160
0161     PartitionGenerator aPartitionGenerator;
0162     std::vector<PartitionGenerator::Partition> partitions = aPartitionGenerator.partitions(data.size());
0163
0164     for (std::vector<PartitionGenerator::Partition>::const_iterator idiv = partitions.begin(); idiv != partitions.end();
0165          idiv++) {
0166       const PartitionGenerator::Partition& partition = *idiv;
0167
0168       std::vector<Combination> subCombinations = this->combinations(data, partition);
0169       for (typename std::vector<Combination>::const_iterator iComb = subCombinations.begin();
0170            iComb != subCombinations.end();
0171            iComb++) {
0172         combinations.push_back(*iComb);
0173       }
0174     }
0175     return combinations;
0176   }
0177
0178 private:
0179   /** Create all combinations obtained by dividing 'data'
0180    *  in two collections, the first one being of size 'sizeFirst'
0181    */
0182   VectorOfCombinations splitInTwoCollections(const Collection& data, int sizeFirst) const {
0183     std::vector<Combination> combinations;
0184     std::stack<Combination> cStack;
0185
0186     // Create first combination with 2 partitions
0187     Combination comb;
0188     comb.push_back(data);
0189     comb.push_back(Collection());
0190     cStack.push(comb);
0191
0192     while (!cStack.empty()) {
0193       Combination combination = cStack.top();
0194       cStack.pop();
0195
0196       Collection collection = combination[0];
0197       std::vector<Combination> subCombinations = separateOneElement(collection);
0198
0199       for (typename std::vector<Combination>::const_iterator iComb = subCombinations.begin();
0200            iComb != subCombinations.end();
0201            iComb++) {
0202         Collection second = combination[1];
0203         second.push_back((*iComb)[1][0]);
0204
0205         // Abandon current combination if not ordered,
0206         // i.e. if previous permutation exists
0207         bool ordered = !prev_permutation(second.begin(), second.end());
0208         if (!ordered)
0209           continue;
0210         next_permutation(second.begin(), second.end());
0211
0212         if ((*iComb)[0].size() == second.size()) {
0213           Collection adjBins;
0214           adjBins.push_back((*iComb)[0][0]);
0215           adjBins.push_back(second[0]);
0216           // Abandon current combination if successive bins of equal size
0217           // not ordered, i.e. if previous permutation exists
0218           if (prev_permutation(adjBins.begin(), adjBins.end()))
0219             continue;
0220         }
0221
0222         Combination stored;
0223         stored.push_back((*iComb)[0]);
0224         stored.push_back(second);
0225
0226         if (stored[0].size() == sizeFirst) {
0227           combinations.push_back(stored);
0228         } else {
0229           cStack.push(stored);
0230         }
0231       }
0232     }
0233     return combinations;
0234   }
0235
0236   /** Create all combinations obtained by dividing 'data' in two collections,
0237    *  the second one having only one element.
0238    */
0239   std::vector<Combination> separateOneElement(const Collection& data) const {
0240     std::vector<Combination> combinations;
0241     for (typename Collection::const_iterator i = data.begin(); i != data.end(); i++) {
0242       Combination comb;
0243       Collection single;
0244       single.push_back(*i);
0245       Collection coll;
0246       typename Collection::const_iterator j = data.begin();
0247       for (; j != i; j++) {
0248         coll.push_back(*j);
0249       }
0250       j++;
0251       for (; j != data.end(); j++) {
0252         coll.push_back(*j);
0253       }
0254       comb.push_back(coll);
0255       comb.push_back(single);
0256       combinations.push_back(comb);
0257     }
0258     return combinations;
0259   }
0260 };
0261
0262 #endif