KrisLibrary  1.0.0
combination.h
Go to the documentation of this file.
1 #ifndef UTILS_COMBINATION_H
2 #define UTILS_COMBINATION_H
3 
4 #include <vector>
5 #include <KrisLibrary/errors.h>
6 
17 
18 inline void FirstCombination(std::vector<int>& v,int n)
19 {
20  int k=(int)v.size();
21  Assert(k <= n);
22  for(int i=0;i<k;i++) v[i]=i;
23 }
24 
25 inline void LastCombination(std::vector<int>& v,int n)
26 {
27  int k=(int)v.size();
28  Assert(k <= n);
29  for(int i=0;i<k;i++) v[i]=i+n-k;
30 }
31 
32 inline int NextCombination(std::vector<int>& v,int n)
33 {
34  int k=(int)v.size();
35  Assert(k <= n);
36  for(int i=k-1;i>=0;i--) {
37  if(v[i] >= i+n-k) { //can't go any farther, loop the previous
38  if(i == 0) {
39  FirstCombination(v,n);
40  return 1;
41  }
42  v[i] = v[i-1]+2;
43  if(v[i] > i+n-k) {
44  FirstCombination(v,n);
45  return 1;
46  }
47  }
48  else {
49  v[i]++;
50  return 0;
51  }
52  }
53  //should never reach here
54  FirstCombination(v,n);
55  return 1;
56 }
57 
58 inline int PrevCombination(std::vector<int>& v,int n)
59 {
60  int k=(int)v.size();
61  Assert(k <= n);
62  for(int i=k-1;i>=0;i--) {
63  if(i > 0) {
64  if(v[i] <= v[i-1]+1) //can't go any farther, loop the previous
65  v[i] = i+n-k;
66  else {
67  v[i]--;
68  return 0;
69  }
70  }
71  else {
72  if(v[i] > 0) {
73  v[i]--;
74  return 0;
75  }
76  else {
77  LastCombination(v,n);
78  return 1;
79  }
80  }
81  }
82  //should never get here
83  LastCombination(v,n);
84  return 1;
85 }
86 
90 {
91  public:
92  inline Combination(int _n) :value(_n,0),n(_n),numCycles(0) { FirstCombination(value,n); }
93  inline Combination(int _k,int _n) :value(_k,0),n(_n),numCycles(0) { Assert(_k <= _n); FirstCombination(value,n); }
94  inline const Combination& operator ++() {
95  numCycles += NextCombination(value,n);
96  return *this;
97  }
98  inline const Combination& operator ++(int) { return operator ++(); }
99  inline const Combination& operator --() {
100  numCycles -= PrevCombination(value,n);
101  return *this;
102  }
103  inline const Combination& operator --(int) { return operator --(); }
104  inline int cycleCount() const { return numCycles; }
105  inline bool isDone() const { return numCycles>0; }
106  inline const std::vector<int>& operator* () const { return value; }
107  inline const std::vector<int>* operator ->() const { return &value; }
108  inline const Combination& operator = (const Combination& c) {
109  value = c.value;
110  n = c.n;
111  numCycles = c.numCycles;
112  return *this;
113  }
114  inline bool operator == (const Combination& c) const { return n == c.n && numCycles == c.numCycles && value == c.value; }
115  inline bool operator < (const Combination& c) const {
116  Assert(n == c.n);
117  if(numCycles < c.numCycles) return true;
118  else if(numCycles > c.numCycles) return false;
119  return std::lexicographical_compare(value.begin(),value.end(),c.value.begin(),c.value.end());
120  }
121 
122  private:
123  std::vector<int> value;
124  int n;
125  int numCycles;
126 };
127 
130 #endif
A class that enumerates combinations.
Definition: combination.h:89