File indexing completed on 2024-04-06 12:01:11
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
0011
0012
0013
0014
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
0026
0027
0028 std::vector<Combination> combinations(const Collection& data, int numberOfCollections) const {
0029 std::vector<Combination> combinations;
0030 Collection sorted = data;
0031
0032
0033 if (prev_permutation(sorted.begin(), sorted.end())) {
0034 sort(sorted.begin(), sorted.end());
0035 }
0036
0037
0038 PartitionGenerator aPartitionGenerator;
0039 std::vector<std::vector<PartitionGenerator::Partition> > partitions =
0040 aPartitionGenerator.sortedPartitions(data.size());
0041
0042
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
0058
0059
0060 std::vector<Combination> combinations(const Collection& data, const PartitionGenerator::Partition& partition) const {
0061 std::vector<Combination> combinations;
0062
0063
0064
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
0074 if (prev_permutation(sortedData.begin(), sortedData.end())) {
0075 sort(sortedData.begin(), sortedData.end());
0076 }
0077
0078
0079 Combination comb;
0080 comb.push_back(sortedData);
0081 if (partition.size() == 1) {
0082
0083 combinations.push_back(comb);
0084 return combinations;
0085 }
0086 std::stack<Combination> cStack;
0087 cStack.push(comb);
0088
0089
0090
0091
0092 PartitionGenerator::Partition sortedPartition = partition;
0093 sort(sortedPartition.begin(), sortedPartition.end(), std::greater_equal<int>());
0094
0095 while (!cStack.empty()) {
0096
0097 Combination combination = cStack.top();
0098 cStack.pop();
0099
0100
0101
0102
0103
0104
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
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
0125
0126 if (prev_permutation(adjBins.begin(), adjBins.end()))
0127 continue;
0128 }
0129 }
0130
0131
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
0140
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
0152
0153 std::vector<Combination> combinations(const Collection& data) const {
0154 std::vector<Combination> combinations;
0155 Collection sorted = data;
0156
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
0180
0181
0182 VectorOfCombinations splitInTwoCollections(const Collection& data, int sizeFirst) const {
0183 std::vector<Combination> combinations;
0184 std::stack<Combination> cStack;
0185
0186
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
0206
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
0217
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
0237
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