CMS 3D CMS Logo

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
List of all members | Public Types | Public Member Functions | Private Member Functions
CombinationGenerator< T > Class Template Reference

#include <CombinationGenerator.h>

Public Types

typedef std::vector< TCollection
 
typedef std::vector< CollectionCombination
 
typedef std::vector< CombinationVectorOfCombinations
 

Public Member Functions

std::vector< Combinationcombinations (const Collection &data) const
 
std::vector< Combinationcombinations (const Collection &data, const PartitionGenerator::Partition &partition) const
 
std::vector< Combinationcombinations (const Collection &data, int numberOfCollections) const
 

Private Member Functions

std::vector< CombinationseparateOneElement (const Collection &data) const
 
VectorOfCombinations splitInTwoCollections (const Collection &data, int sizeFirst) const
 

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 18 of file CombinationGenerator.h.

Member Typedef Documentation

◆ Collection

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

Definition at line 20 of file CombinationGenerator.h.

◆ Combination

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

Definition at line 22 of file CombinationGenerator.h.

◆ VectorOfCombinations

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

Definition at line 23 of file CombinationGenerator.h.

Member Function Documentation

◆ combinations() [1/3]

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

Create all combinations of elements from 'data'.

Definition at line 153 of file CombinationGenerator.h.

153  {
154  std::vector<Combination> combinations;
155  Collection sorted = data;
156  // Sort if needed
157  if (prev_permutation(sorted.begin(), sorted.end())) {
158  sort(sorted.begin(), sorted.end());
159  }
160 
161  PartitionGenerator aPartitionGenerator;
162  std::vector<PartitionGenerator::Partition> partitions = aPartitionGenerator.partitions(data.size());
163 
164  for (std::vector<PartitionGenerator::Partition>::const_iterator idiv = partitions.begin(); idiv != partitions.end();
165  idiv++) {
166  const PartitionGenerator::Partition& partition = *idiv;
167 
168  std::vector<Combination> subCombinations = this->combinations(data, partition);
169  for (typename std::vector<Combination>::const_iterator iComb = subCombinations.begin();
170  iComb != subCombinations.end();
171  iComb++) {
172  combinations.push_back(*iComb);
173  }
174  }
175  return combinations;
176  }

References CombinationGenerator< T >::combinations(), data, and PartitionGenerator::partitions().

◆ combinations() [2/3]

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

60  {
61  std::vector<Combination> combinations;
62 
63  // Check that sum of collection sizes in 'partition'
64  // amounts to number of elements in 'data'
65  int nElts = 0;
66  for (PartitionGenerator::Partition::const_iterator iSize = partition.begin(); iSize != partition.end(); iSize++) {
67  nElts += *iSize;
68  }
69  if (nElts != data.size())
70  return combinations;
71 
72  Collection sortedData = data;
73  // Sort if needed
74  if (prev_permutation(sortedData.begin(), sortedData.end())) {
75  sort(sortedData.begin(), sortedData.end());
76  }
77 
78  // Create initial combination and put it on the stack
80  comb.push_back(sortedData);
81  if (partition.size() == 1) {
82  // Return only one combination with only one collection
83  combinations.push_back(comb);
84  return combinations;
85  }
86  std::stack<Combination> cStack;
87  cStack.push(comb);
88 
89  // Sort partitions by size
90  // Let 'sortedPartition' = ( n0, n1,... nk, nk+1,... nm )
91  // Ordering is >= to speed up partitioning: n0 >= n1 >=... >= nm
92  PartitionGenerator::Partition sortedPartition = partition;
93  sort(sortedPartition.begin(), sortedPartition.end(), std::greater_equal<int>());
94 
95  while (!cStack.empty()) {
96  // 'combination' popped out of the stack
97  Combination combination = cStack.top();
98  cStack.pop();
99 
100  // At this stage 'combination' is made of collections
101  // of sizes ( n0+n1+...+nk, nk+1,... nm )
102  // Now generate all combinations obtained by splitting
103  // the first collection of 'combination' in two,
104  // according to Partition 'biPartition' = (n0+n1+...+nk-1, nk)
105  int k = sortedPartition.size() - combination.size();
106  int size = 0;
107  for (int iColl = 0; iColl != k; iColl++) {
108  size += sortedPartition[iColl];
109  }
110  PartitionGenerator::Partition biPartition(2);
111  biPartition[0] = size;
112  biPartition[1] = sortedPartition[k];
113 
114  VectorOfCombinations subCombinations = splitInTwoCollections(combination[0], biPartition[0]);
115  for (typename std::vector<Combination>::const_iterator iComb = subCombinations.begin();
116  iComb != subCombinations.end();
117  iComb++) {
118  // Check ordering of successive bins of equal size
119  if (combination.size() > 1) {
120  if ((*iComb)[1].size() == combination[1].size()) {
121  Collection adjBins;
122  adjBins.push_back((*iComb)[1][0]);
123  adjBins.push_back(combination[1][0]);
124  // Drop 'combination' if successive bins of equal size not ordered
125  // i.e. if previous permutation exists
126  if (prev_permutation(adjBins.begin(), adjBins.end()))
127  continue;
128  }
129  }
130 
131  // Append remaining collections of 'combination'
132  Combination merged = *iComb;
133  typename Combination::const_iterator it = combination.begin();
134  it++;
135  for (; it != combination.end(); it++) {
136  merged.push_back(*it);
137  }
138 
139  // Store combination 'merged' if partitioning is complete,
140  // otherwise put it on the stack for further partitioning.
141  if (merged.size() == sortedPartition.size()) {
142  combinations.push_back(merged);
143  } else {
144  cStack.push(merged);
145  }
146  }
147  }
148  return combinations;
149  }

References bookConverter::comb, CombinationGenerator< T >::combinations(), data, dqmdumpme::k, findQualityFiles::size, and CombinationGenerator< T >::splitInTwoCollections().

◆ combinations() [3/3]

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

28  {
29  std::vector<Combination> combinations;
30  Collection sorted = data;
31 
32  // Sort if needed
33  if (prev_permutation(sorted.begin(), sorted.end())) {
34  sort(sorted.begin(), sorted.end());
35  }
36 
37  // Create sorted partitions
38  PartitionGenerator aPartitionGenerator;
39  std::vector<std::vector<PartitionGenerator::Partition> > partitions =
40  aPartitionGenerator.sortedPartitions(data.size());
41 
42  // Use partitions of size 'numberOfCollections' only
43  for (std::vector<PartitionGenerator::Partition>::const_iterator idiv = partitions[numberOfCollections - 1].begin();
44  idiv != partitions[numberOfCollections - 1].end();
45  idiv++) {
46  const PartitionGenerator::Partition& partition = *idiv;
47  std::vector<Combination> subCombinations = this->combinations(data, partition);
48  for (typename std::vector<Combination>::const_iterator iComb = subCombinations.begin();
49  iComb != subCombinations.end();
50  iComb++) {
51  combinations.push_back(*iComb);
52  }
53  }
54  return combinations;
55  }

References data, and PartitionGenerator::sortedPartitions().

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

◆ separateOneElement()

template<class T >
std::vector<Combination> CombinationGenerator< T >::separateOneElement ( const Collection data) const
inlineprivate

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

Definition at line 239 of file CombinationGenerator.h.

239  {
240  std::vector<Combination> combinations;
241  for (typename Collection::const_iterator i = data.begin(); i != data.end(); i++) {
244  single.push_back(*i);
245  Collection coll;
246  typename Collection::const_iterator j = data.begin();
247  for (; j != i; j++) {
248  coll.push_back(*j);
249  }
250  j++;
251  for (; j != data.end(); j++) {
252  coll.push_back(*j);
253  }
254  comb.push_back(coll);
255  comb.push_back(single);
256  combinations.push_back(comb);
257  }
258  return combinations;
259  }

References bookConverter::comb, CombinationGenerator< T >::combinations(), data, mps_fire::i, dqmiolumiharvest::j, and trackerHitRTTI::single.

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

◆ splitInTwoCollections()

template<class T >
VectorOfCombinations CombinationGenerator< T >::splitInTwoCollections ( const Collection data,
int  sizeFirst 
) const
inlineprivate

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

Definition at line 182 of file CombinationGenerator.h.

182  {
183  std::vector<Combination> combinations;
184  std::stack<Combination> cStack;
185 
186  // Create first combination with 2 partitions
188  comb.push_back(data);
189  comb.push_back(Collection());
190  cStack.push(comb);
191 
192  while (!cStack.empty()) {
193  Combination combination = cStack.top();
194  cStack.pop();
195 
196  Collection collection = combination[0];
197  std::vector<Combination> subCombinations = separateOneElement(collection);
198 
199  for (typename std::vector<Combination>::const_iterator iComb = subCombinations.begin();
200  iComb != subCombinations.end();
201  iComb++) {
202  Collection second = combination[1];
203  second.push_back((*iComb)[1][0]);
204 
205  // Abandon current combination if not ordered,
206  // i.e. if previous permutation exists
207  bool ordered = !prev_permutation(second.begin(), second.end());
208  if (!ordered)
209  continue;
210  next_permutation(second.begin(), second.end());
211 
212  if ((*iComb)[0].size() == second.size()) {
213  Collection adjBins;
214  adjBins.push_back((*iComb)[0][0]);
215  adjBins.push_back(second[0]);
216  // Abandon current combination if successive bins of equal size
217  // not ordered, i.e. if previous permutation exists
218  if (prev_permutation(adjBins.begin(), adjBins.end()))
219  continue;
220  }
221 
222  Combination stored;
223  stored.push_back((*iComb)[0]);
224  stored.push_back(second);
225 
226  if (stored[0].size() == sizeFirst) {
227  combinations.push_back(stored);
228  } else {
229  cStack.push(stored);
230  }
231  }
232  }
233  return combinations;
234  }

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

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

bookConverter.comb
comb
Definition: bookConverter.py:145
CombinationGenerator::splitInTwoCollections
VectorOfCombinations splitInTwoCollections(const Collection &data, int sizeFirst) const
Definition: CombinationGenerator.h:182
mps_fire.i
i
Definition: mps_fire.py:428
PartitionGenerator::sortedPartitions
std::vector< std::vector< Partition > > sortedPartitions(int collectionSize, int minCollectionSize=1) const
Definition: PartitionGenerator.cc:34
CombinationGenerator::Collection
std::vector< T > Collection
Definition: CombinationGenerator.h:20
edm::second
U second(std::pair< T, U > const &p)
Definition: ParameterSet.cc:222
CombinationGenerator::VectorOfCombinations
std::vector< Combination > VectorOfCombinations
Definition: CombinationGenerator.h:23
PartitionGenerator
Definition: PartitionGenerator.h:12
AlignmentPI::partitions
partitions
Definition: AlignmentPayloadInspectorHelper.h:48
CombinationGenerator::combinations
std::vector< Combination > combinations(const Collection &data, int numberOfCollections) const
Definition: CombinationGenerator.h:28
dqmdumpme.k
k
Definition: dqmdumpme.py:60
CombinationGenerator::separateOneElement
std::vector< Combination > separateOneElement(const Collection &data) const
Definition: CombinationGenerator.h:239
CombinationGenerator::Combination
std::vector< Collection > Combination
Definition: CombinationGenerator.h:22
PartitionGenerator::partitions
std::vector< Partition > partitions(int collectionSize, int minCollectionSize=1) const
Definition: PartitionGenerator.cc:6
trackerHitRTTI::single
Definition: trackerHitRTTI.h:10
universalConfigTemplate.collection
collection
Definition: universalConfigTemplate.py:81
PartitionGenerator::Partition
std::vector< int > Partition
Definition: PartitionGenerator.h:14
data
char data[epos_bytes_allocation]
Definition: EPOS_Wrapper.h:79
dqmiolumiharvest.j
j
Definition: dqmiolumiharvest.py:66
findQualityFiles.size
size
Write out results.
Definition: findQualityFiles.py:443