Empirical
combos.h
Go to the documentation of this file.
1 
20 #ifndef EMP_COMBOS_H
21 #define EMP_COMBOS_H
22 
23 #include <iostream>
24 
25 #include "../base/assert.h"
26 #include "../base/vector.h"
27 
28 namespace emp {
29 
30  class ComboIDs {
31  private:
32  size_t max_count;
33  emp::vector<size_t> cur_combo;
34  emp::vector<size_t> max_combo;
35  size_t num_combos;
36 
37  static size_t CountCombos(size_t max_count, size_t combo_size);
38  public:
39  ComboIDs(size_t in_max, size_t combo_size);
40  ~ComboIDs() { ; }
41 
42  // Accessors
43  const emp::vector<size_t> & GetCombo() const { return cur_combo; }
44  const emp::vector<size_t> & GetMaxCombo() const { return max_combo; }
45  size_t GetComboSize() const { return cur_combo.size(); }
46  size_t GetNumCombos() const { return num_combos; }
47 
48  size_t & operator[](const size_t index) { return cur_combo[index]; }
49  const size_t & operator[](const size_t index) const { return cur_combo[index]; }
50 
51  // General Use manipulatros
52  const emp::vector<size_t> & Reset();
53  bool NextCombo();
54  void ResizeCombos(size_t new_size);
55 
56  // Deal with inversions...
58 
59  // Make sure obvious operators also work plus standatd library compatability.
60  ComboIDs & operator++() { NextCombo(); return *this; }
61  ComboIDs & operator++(int) { NextCombo(); return *this; }
62  size_t size() { return num_combos; }
63  };
64 
65  ComboIDs::ComboIDs(size_t in_max, size_t combo_size)
66  : max_count(in_max), cur_combo(combo_size), max_combo(combo_size),
67  num_combos(CountCombos(in_max, combo_size))
68  {
69  emp_assert(combo_size <= in_max);
70  const size_t diff = in_max - combo_size;
71  for (size_t i = 0; i < cur_combo.size(); i++) {
72  cur_combo[i] = i;
73  max_combo[i] = i+diff;
74  }
75  }
76 
78  {
79  for (size_t i = 0; i < cur_combo.size(); i++) {
80  cur_combo[i] = i;
81  }
82  return cur_combo;
83  }
84 
86  {
87  size_t inc_pos = cur_combo.size() - 1;
88  cur_combo[inc_pos]++;
89 
90  // Increase the first position that we can without it going over the max.
91  while (inc_pos > 0 && cur_combo[inc_pos] > max_combo[inc_pos]) {
92  inc_pos--;
93  cur_combo[inc_pos]++;
94  }
95 
96  // If we were already on the last combo, reset to the beginning.
97  if (cur_combo[0] > max_combo[0]) {
98  Reset();
99  return false;
100  }
101 
102  // Update all of the positions after the current one.
103  for (size_t i = inc_pos + 1; i < cur_combo.size(); i++) {
104  cur_combo[i] = cur_combo[i-1] + 1;
105  }
106 
107  return true;
108  }
109 
110  void ComboIDs::ResizeCombos(size_t new_size)
111  {
112  emp_assert(new_size < max_count);
113 
114  // Reset internal state...
115  cur_combo.resize(new_size);
116  max_combo.resize(new_size);
117  num_combos = CountCombos(max_count, new_size);
118 
119  const size_t diff = max_count - new_size;
120  for (size_t i = 0; i < new_size; i++) {
121  cur_combo[i] = i;
122  max_combo[i] = i+diff;
123  }
124  }
125 
126 
128  {
129  size_t inverse_size = max_count - cur_combo.size();
130  emp::vector<size_t> inverse_combo(inverse_size);
131 
132  size_t norm_pos = 0;
133  size_t inv_pos = 0;
134  for (size_t i = 0; i < max_count; i++) {
135  if (norm_pos < cur_combo.size() && cur_combo[norm_pos] == i) {
136  norm_pos++; // Found in cur combo...
137  } else inverse_combo[inv_pos++] = i; // Not in cur; put in inverse.
138  }
139  return inverse_combo;
140  }
141 
142 
143  size_t ComboIDs::CountCombos(size_t max_count, size_t combo_size)
144  {
145  if (combo_size * 2 > max_count) combo_size = max_count - combo_size;
146 
147  size_t choose_product = 1;
148  size_t total_product = 1;
149  for (size_t i = 0; i < combo_size; i++) {
150  choose_product *= i+1;
151  total_product *= max_count - i;
152  }
153 
154  return total_product / choose_product;
155  }
156 
157 }
158 
159 #endif
~ComboIDs()
Definition: combos.h:40
bool NextCombo()
Definition: combos.h:85
const emp::vector< size_t > & GetMaxCombo() const
Definition: combos.h:44
size_t size() const
Definition: vector.h:151
const emp::vector< size_t > & GetCombo() const
Definition: combos.h:43
size_t size()
Definition: combos.h:62
emp::vector< size_t > GetInverseCombo()
Definition: combos.h:127
ComboIDs & operator++(int)
Definition: combos.h:61
const size_t & operator[](const size_t index) const
Definition: combos.h:49
Definition: combos.h:30
void resize(size_t new_size)
Definition: vector.h:161
size_t GetNumCombos() const
Definition: combos.h:46
If we are in emscripten, make sure to include the header.
Definition: array.h:37
const emp::vector< size_t > & Reset()
Definition: combos.h:77
#define emp_assert(...)
Definition: assert.h:199
ComboIDs & operator++()
Definition: combos.h:60
ComboIDs(size_t in_max, size_t combo_size)
Definition: combos.h:65
size_t GetComboSize() const
Definition: combos.h:45
size_t & operator[](const size_t index)
Definition: combos.h:48
void ResizeCombos(size_t new_size)
Definition: combos.h:110