CMS 3D CMS Logo
List of all members | Public Member Functions | Private Member Functions | Private Attributes
Combinatorics Class Reference

#include <Combinatorics.h>

Public Member Functions

 Combinatorics (Int_t Set, Int_t Subset)
 
Int_t EqualPermutation (const std::vector< UInt_t > &permutation1, const std::vector< UInt_t > &permutation2)
 
Int_t EqualPermutation_2_0 (const std::vector< UInt_t > &permutation1, const std::vector< UInt_t > &permutation2)
 
Int_t EqualPermutation_2_2 (const std::vector< UInt_t > &permutation1, const std::vector< UInt_t > &permutation2)
 
Int_t EqualPermutation_N_1 (const std::vector< UInt_t > &permutation1, const 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 (const std::vector< std::vector< UInt_t > > &permutations)
 
void Print (const 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 (const std::vector< UInt_t > &permutation, UInt_t digits)
 
void Skip_2_0 (const std::vector< std::vector< UInt_t > > &permutation1, std::vector< std::vector< UInt_t > > &permutation2)
 
void Skip_2_2 (const 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::Combinatorics ( Int_t  Set,
Int_t  Subset 
)

Definition at line 19 of file Combinatorics.cc.

20  :
21 
22  m_SetQuantity(SetQuantity),
23  m_SubsetQuantity(SubsetQuantity) {
24  // Get permutations
25  CalculatePermutations();
26 }

References CalculatePermutations().

◆ ~Combinatorics()

Combinatorics::~Combinatorics ( )
virtual

Definition at line 31 of file Combinatorics.cc.

31 {}

Member Function Documentation

◆ CalculatePermutations()

Int_t Combinatorics::CalculatePermutations ( )
private

Definition at line 41 of file Combinatorics.cc.

41  {
42  if (m_SetQuantity < 1 || m_SubsetQuantity < 1 || (m_SetQuantity < m_SubsetQuantity)) {
43  edm::LogWarning("Combinatorics") << "[Combinatorics] No valid choice of set or subset!" << endl;
44  return -1;
45  }
46 
47  Int_t* currentSubset = new Int_t[m_SubsetQuantity];
48  Int_t* currentMapping = new Int_t[m_SetQuantity];
49 
50  initial_subset(m_SubsetQuantity, currentSubset);
51  do {
52  initial_permutation(m_SetQuantity, currentMapping);
53  do {
54  for (UShort_t i = 0; i < m_SubsetQuantity; i++) {
55  m_Subset.push_back(currentSubset[currentMapping[i]]);
56  }
57  m_Permutations.push_back(m_Subset);
58  m_Subset.clear();
59  } while (next_permutation(m_SubsetQuantity, currentMapping));
60  } while (next_subset(m_SetQuantity, m_SubsetQuantity, currentSubset));
61 
62  delete[] currentSubset;
63  delete[] currentMapping;
64 
65  return 0;
66 }

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

Referenced by Combinatorics().

◆ EqualPermutation()

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

Definition at line 179 of file Combinatorics.cc.

179  {
180  if (p1.size() != p2.size()) {
181  edm::LogWarning("Combinatorics") << "[Combinatorics::EqualPermutation] permutations have different size!" << endl;
182  return -1;
183  }
184 
185  Float_t p1_sum = 0.0;
186  Float_t p2_sum = 0.0;
187 
188  // Check whether permutations are equal (2^index)
189  for (UInt_t i = 0; i < p1.size(); i++)
190  p1_sum += (1 << p1.at(i));
191  for (UInt_t i = 0; i < p2.size(); i++)
192  p2_sum += (1 << p2.at(i));
193 
194  return (p1_sum == p2_sum ? 1 : 0);
195 }

References mps_fire::i, p1, and p2.

Referenced by EqualPermutation_N_1(), and GetCombinations().

◆ EqualPermutation_2_0()

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

Definition at line 297 of file Combinatorics.cc.

297  {
298  if (p1.size() < 2) {
299  edm::LogWarning("Combinatorics") << "[Combinatorics::EqualPermutation_2_0] permutation has wrong size!" << endl;
300  return -1;
301  }
302 
303  // Check whether permutations are equal
304  if (((1 << p1.at(0)) + (1 << p1.at(1)) == (1 << p2.at(0)) + (1 << p2.at(1))) && p1.at(2) == p2.at(2) &&
305  p1.at(3) == p2.at(3)) {
306  return 1;
307  }
308  return 0;
309 }

References p1, and p2.

Referenced by Skip_2_0().

◆ EqualPermutation_2_2()

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

Definition at line 315 of file Combinatorics.cc.

315  {
316  // Returns true if two permutations of four "int" are equal
317  // (equal means e.g.: 0123 = 1023 = 0132 = 1032)
318 
319  if (p1.size() != 4 && p2.size() != 4) {
320  edm::LogWarning("Combinatorics") << "[Combinatorics::EqualPermutationTwoByTwo] permutation(s) have wrong size!"
321  << endl;
322  return -1;
323  }
324 
325  // Check whether permutations are equal (2^index)
326  if (((1 << p1.at(0)) + (1 << p1.at(1)) == (1 << p2.at(0)) + (1 << p2.at(1))) &&
327  ((1 << p1.at(2)) + (1 << p1.at(3)) == (1 << p2.at(2)) + (1 << p2.at(3)))) {
328  return 1;
329  }
330  return 0;
331 }

References p1, and p2.

Referenced by Skip_2_2().

◆ EqualPermutation_N_1()

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

Definition at line 337 of file Combinatorics.cc.

337  {
338  // Returns true if two permutations of four "int" are equal
339  // (equal means e.g.: 012 = 102)
340 
341  if (p1.size() != p2.size()) {
342  edm::LogWarning("Combinatorics") << "[Combinatorics::EqualPermutationTwoByTwo] permutation(s) have wrong size!"
343  << endl;
344  return -1;
345  }
346 
347  return (EqualPermutation(p1, p2) && p1.back() == p2.back() ? 1 : 0);
348 }

References EqualPermutation(), p1, and p2.

◆ GetCombinations()

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

Definition at line 159 of file Combinatorics.cc.

159  {
160  if (m_Permutations.empty()) {
161  LogDebug("Combinatorics") << "Nothing to do." << endl;
162  return m_Combinations;
163  }
164 
165  m_Combinations.push_back(m_Permutations.at(0));
166 
167  for (UInt_t i = 1; i < m_Permutations.size(); i++) {
168  if (!EqualPermutation(m_Combinations.back(), m_Permutations.at(i))) {
169  m_Combinations.push_back(m_Permutations.at(i));
170  }
171  }
172  return m_Combinations;
173 }

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

Referenced by Tau3MuReco::findCorrectPairing(), and GetCombinations_N_1().

◆ GetCombinations_2_0()

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

Definition at line 230 of file Combinatorics.cc.

230  {
231  // combination vector returned
232  vector<vector<UInt_t> > FinalCombinations;
233 
234  if (m_Permutations.empty()) {
235  LogDebug("Combinatorics") << "[Combinatorics::GetCombinations_2_0] Nothing to do." << endl;
236  return FinalCombinations;
237  }
238 
239  // So far only for subsets of four indices
240  if (m_SubsetQuantity != 4) {
241  edm::LogWarning("Combinatorics") << "[Combinatorics::GetCombinations_2_0] Subset must be 4." << endl;
242  return FinalCombinations;
243  }
244 
245  // Skip specific permutations
246  Skip_2_0(m_Permutations, FinalCombinations);
247 
248  return FinalCombinations;
249 }

References LogDebug, m_Permutations, m_SubsetQuantity, and Skip_2_0().

◆ GetCombinations_2_2()

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

Definition at line 203 of file Combinatorics.cc.

203  {
204  // combination vector returned
205  vector<vector<UInt_t> > FinalCombinations;
206 
207  if (m_Permutations.empty()) {
208  LogDebug("Combinatorics") << "[Combinatorics::GetCombinations_2_2] Nothing to do." << endl;
209  return FinalCombinations;
210  }
211 
212  // So far only for subsets of four indices
213  if (m_SubsetQuantity != 4) {
214  edm::LogWarning("Combinatorics") << "[Combinatorics::GetCombinations_2_2] Subset must be 4." << endl;
215  return FinalCombinations;
216  }
217 
218  // Skip specific permutations
219  Skip_2_2(m_Permutations, FinalCombinations);
220 
221  return FinalCombinations;
222 }

References LogDebug, m_Permutations, m_SubsetQuantity, and Skip_2_2().

◆ GetCombinations_N_1()

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

Definition at line 353 of file Combinatorics.cc.

353  {
354  // Get combinations
355  m_Combinations.clear();
356  GetCombinations();
357 
358  // combination vector returned
359  vector<vector<UInt_t> > FinalCombinations;
360 
361  if (m_Combinations.empty()) {
362  LogDebug("Combinatorics") << "[Combinatorics::GetCombinationsThreeByOne] Nothing to do." << endl;
363  return FinalCombinations;
364  }
365 
366  for (UInt_t i = 0; i < m_Combinations.size(); i++) {
367  vector<UInt_t> RotatingPermutation = m_Combinations.at(i);
368  FinalCombinations.push_back(m_Combinations.at(i));
369 
370  for (UInt_t j = 1; j < RotatingPermutation.size(); j++) {
371  FinalCombinations.push_back(Rotate(RotatingPermutation, j));
372  }
373  }
374  return FinalCombinations;
375 }

References GetCombinations(), mps_fire::i, dqmiolumiharvest::j, LogDebug, m_Combinations, and Rotate().

◆ GetPermutations()

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

Definition at line 36 of file Combinatorics.cc.

36 { return m_Permutations; }

References m_Permutations.

◆ initial_permutation()

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

Definition at line 71 of file Combinatorics.cc.

71  {
72  for (int i = 0; i < size; i++) {
73  permutation[i] = i;
74  }
75 }

References mps_fire::i, and findQualityFiles::size.

Referenced by CalculatePermutations().

◆ initial_subset()

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

Definition at line 80 of file Combinatorics.cc.

80  {
81  for (int i = 0; i < k; i++) {
82  subset[i] = i;
83  }
84 }

References mps_fire::i, and dqmdumpme::k.

Referenced by CalculatePermutations().

◆ next_permutation()

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

Definition at line 89 of file Combinatorics.cc.

89  {
90  int i, j, k;
91  if (size < 2)
92  return false;
93  i = size - 2;
94 
95  while ((permutation[i] > permutation[i + 1]) && (i != 0)) {
96  i--;
97  }
98  if ((i == 0) && (permutation[0] > permutation[1]))
99  return false;
100 
101  k = i + 1;
102  for (j = i + 2; j < size; j++) {
103  if ((permutation[j] > permutation[i]) && (permutation[j] < permutation[k])) {
104  k = j;
105  }
106  }
107 
108  // swap i and k
109  {
110  int tmp = permutation[i];
111  permutation[i] = permutation[k];
112  permutation[k] = tmp;
113  }
114 
115  for (j = i + 1; j <= ((size + i) / 2); j++) {
116  int tmp = permutation[j];
117  permutation[j] = permutation[size + i - j];
118  permutation[size + i - j] = tmp;
119  }
120 
121  // return whether a next permutation exists
122  return true;
123 }

References mps_fire::i, dqmiolumiharvest::j, dqmdumpme::k, findQualityFiles::size, and createJobs::tmp.

Referenced by CalculatePermutations().

◆ next_subset()

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

Definition at line 131 of file Combinatorics.cc.

131  {
132  int i;
133  int j;
134  int jsave;
135  bool done;
136 
137  if (subset[0] < n - k) {
138  done = false;
139  jsave = k - 1;
140  for (j = 0; j < k - 1; j++) {
141  if (subset[j] + 1 < subset[j + 1]) {
142  jsave = j;
143  break;
144  }
145  }
146  for (i = 0; i < jsave; i++)
147  subset[i] = i;
148  subset[jsave] = subset[jsave] + 1;
149  } else {
150  done = true;
151  }
152  // return whether a next subset exists
153  return !done;
154 }

References fileCollector::done, mps_fire::i, dqmiolumiharvest::j, dqmdumpme::k, and dqmiodumpmetadata::n.

Referenced by CalculatePermutations().

◆ Print() [1/2]

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

Definition at line 416 of file Combinatorics.cc.

416  {
417  LogDebug("Combinatorics") << "**************" << endl;
418  LogDebug("Combinatorics") << "Permutations: " << p.size() << endl;
419 
420  // Print permutations
421  for (UShort_t i = 0; i < p.size(); i++) {
422  for (UShort_t j = 0; j < (p.at(0)).size(); j++)
423  LogDebug("Combinatorics") << (p.at(i)).at(j);
424  LogDebug("Combinatorics") << endl;
425  }
426 }

References mps_fire::i, dqmiolumiharvest::j, LogDebug, AlCaHLTBitMon_ParallelJobs::p, and findQualityFiles::size.

◆ Print() [2/2]

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

Definition at line 405 of file Combinatorics.cc.

405  {
406  // Print permutations
407  for (UShort_t i = 0; i < p.size(); i++) {
408  LogDebug("Combinatorics") << (p.at(i));
409  }
410  LogDebug("Combinatorics") << endl;
411 }

References mps_fire::i, LogDebug, and AlCaHLTBitMon_ParallelJobs::p.

◆ Rotate()

vector< UInt_t > Combinatorics::Rotate ( const std::vector< UInt_t > &  permutation,
UInt_t  digits 
)
private

Definition at line 380 of file Combinatorics.cc.

380  {
381  vector<UInt_t> p;
382  vector<UInt_t> tmp;
383 
384  if (permutation.size() <= digm_) {
385  edm::LogWarning("Combinatorics") << "[Combinatorics::Rotate] WARNING: More rotations than digm_ in permutation!"
386  << endl;
387  }
388 
389  // Save the first i digm_
390  for (UInt_t i = 0; i < digm_; i++) {
391  tmp.push_back(permutation.at(i));
392  }
393  for (UInt_t j = 0; j < permutation.size() - digm_; j++) {
394  p.push_back(permutation.at(j + digm_));
395  }
396  for (UInt_t k = 0; k < digm_; k++)
397  p.push_back(tmp.at(k));
398 
399  return p;
400 }

References mps_fire::i, dqmiolumiharvest::j, dqmdumpme::k, AlCaHLTBitMon_ParallelJobs::p, and createJobs::tmp.

Referenced by GetCombinations_N_1().

◆ Skip_2_0()

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

Definition at line 254 of file Combinatorics.cc.

254  {
255  Bool_t Skip = kFALSE;
256 
257  p2.push_back(p1.at(0));
258 
259  for (UShort_t i = 1; i < p1.size(); i++) {
260  for (UShort_t j = 0; j < p2.size(); j++) {
261  if (EqualPermutation_2_0(p1.at(i), p2.at(j))) {
262  Skip = kTRUE;
263  }
264  }
265  if (!Skip)
266  p2.push_back(p1.at(i));
267 
268  Skip = kFALSE;
269  }
270 }

References EqualPermutation_2_0(), mps_fire::i, dqmiolumiharvest::j, p1, and p2.

Referenced by GetCombinations_2_0().

◆ Skip_2_2()

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

Definition at line 275 of file Combinatorics.cc.

275  {
276  Bool_t Skip = kFALSE;
277 
278  p2.push_back(p1.at(0));
279 
280  for (UShort_t i = 1; i < p1.size(); i++) {
281  for (UShort_t j = 0; j < p2.size(); j++) {
282  if (EqualPermutation_2_2(p1.at(i), p2.at(j))) {
283  Skip = kTRUE;
284  }
285  }
286  if (!Skip)
287  p2.push_back(p1.at(i));
288 
289  Skip = kFALSE;
290  }
291 }

References EqualPermutation_2_2(), mps_fire::i, dqmiolumiharvest::j, p1, and p2.

Referenced by GetCombinations_2_2().

Member Data Documentation

◆ m_Combinations

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

Definition at line 54 of file Combinatorics.h.

Referenced by GetCombinations(), and GetCombinations_N_1().

◆ m_Permutations

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

Definition at line 53 of file Combinatorics.h.

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

◆ m_SetQuantity

const Int_t Combinatorics::m_SetQuantity
private

Definition at line 49 of file Combinatorics.h.

Referenced by CalculatePermutations().

◆ m_Subset

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

Definition at line 52 of file Combinatorics.h.

Referenced by CalculatePermutations().

◆ m_SubsetQuantity

const Int_t Combinatorics::m_SubsetQuantity
private

Definition at line 50 of file Combinatorics.h.

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

Combinatorics::Rotate
std::vector< UInt_t > Rotate(const std::vector< UInt_t > &permutation, UInt_t digits)
Definition: Combinatorics.cc:380
mps_fire.i
i
Definition: mps_fire.py:428
dqmiodumpmetadata.n
n
Definition: dqmiodumpmetadata.py:28
Combinatorics::Skip_2_2
void Skip_2_2(const std::vector< std::vector< UInt_t > > &permutation1, std::vector< std::vector< UInt_t > > &permutation2)
Definition: Combinatorics.cc:275
Combinatorics::CalculatePermutations
Int_t CalculatePermutations()
Definition: Combinatorics.cc:41
Combinatorics::m_SubsetQuantity
const Int_t m_SubsetQuantity
Definition: Combinatorics.h:50
AlCaHLTBitMon_ParallelJobs.p
p
Definition: AlCaHLTBitMon_ParallelJobs.py:153
Combinatorics::m_Subset
std::vector< UInt_t > m_Subset
Definition: Combinatorics.h:52
createJobs.tmp
tmp
align.sh
Definition: createJobs.py:716
edm::LogWarning
Log< level::Warning, false > LogWarning
Definition: MessageLogger.h:122
Combinatorics::initial_subset
void initial_subset(int k, int *subset)
Definition: Combinatorics.cc:80
fileCollector.done
done
Definition: fileCollector.py:123
Combinatorics::next_subset
Bool_t next_subset(int n, int k, int *subset)
Definition: Combinatorics.cc:131
Combinatorics::EqualPermutation_2_2
Int_t EqualPermutation_2_2(const std::vector< UInt_t > &permutation1, const std::vector< UInt_t > &permutation2)
Definition: Combinatorics.cc:315
p2
double p2[4]
Definition: TauolaWrapper.h:90
dqmdumpme.k
k
Definition: dqmdumpme.py:60
Combinatorics::Skip_2_0
void Skip_2_0(const std::vector< std::vector< UInt_t > > &permutation1, std::vector< std::vector< UInt_t > > &permutation2)
Definition: Combinatorics.cc:254
LogDebug
#define LogDebug(id)
Definition: MessageLogger.h:223
Combinatorics::GetCombinations
std::vector< std::vector< UInt_t > > GetCombinations()
Definition: Combinatorics.cc:159
p1
double p1[4]
Definition: TauolaWrapper.h:89
Combinatorics::m_SetQuantity
const Int_t m_SetQuantity
Definition: Combinatorics.h:49
Combinatorics::m_Combinations
std::vector< std::vector< UInt_t > > m_Combinations
Definition: Combinatorics.h:54
Combinatorics::m_Permutations
std::vector< std::vector< UInt_t > > m_Permutations
Definition: Combinatorics.h:53
Combinatorics::initial_permutation
void initial_permutation(int size, int *permutation)
Definition: Combinatorics.cc:71
Combinatorics::EqualPermutation
Int_t EqualPermutation(const std::vector< UInt_t > &permutation1, const std::vector< UInt_t > &permutation2)
Definition: Combinatorics.cc:179
Combinatorics::EqualPermutation_2_0
Int_t EqualPermutation_2_0(const std::vector< UInt_t > &permutation1, const std::vector< UInt_t > &permutation2)
Definition: Combinatorics.cc:297
dqmiolumiharvest.j
j
Definition: dqmiolumiharvest.py:66
Combinatorics::next_permutation
Bool_t next_permutation(int size, int *permutation)
Definition: Combinatorics.cc:89
findQualityFiles.size
size
Write out results.
Definition: findQualityFiles.py:443
Generated for CMSSW Reference Manual by doxygen 1.8.16