License Public Domain
Lines 202
Included in this Library
Permissions
Viewable by Everyone
Editable by All Siafoo Users
Hide
Writing an article is easy - try our reStructured Text demo Join Siafoo Now or Learn More

combEngine.cpp Atom Feed 0

In Brief Here is the corresponding function code.
# 's
  1// -*- C++ -*-
2#include <iostream>
3#include <fstream>
4#include <iomanip>
5#include <assert.h>
6#include <math.h>
7#include "combEngine.h"
8
9using namespace std;
10
11CombEngine::CombEngine (int from, int choose, int startAt)
12{
13 m_startAt = startAt;
14 setFromAndChoose (from, choose);
15}
16
17void
18CombEngine::setFromAndChoose (int from, int choose)
19{
20 // check our values
21 if ((from <= 0) || (choose <= 0) || (from < choose))
22 {
23 cerr << "Error: CombEngine::setFromAndChoose: Invalid initialization"
24 << endl;
25 assert(0);
26 }
27 m_from = from;
28 m_choose = choose;
29 m_combinations = factorialRatio (m_from, m_from - choose);
30 _setupDefaultVector();
31 _setupDecodingVector();
32}
33
34
35CombEngine::IVec
36CombEngine::combination (long long nth) const
37{
38 IVec retval;
39 reset();
40 // loop over decoding vector
41 int size = (int) m_decodeVec.size(); // same as m_choose
42 for (int loop = 0; loop < size; ++loop)
43 {
44 long long value = m_decodeVec[loop];
45 int which = nth / value;
46 int one = _getNthComponent (which);
47 retval.push_back (one);
48 nth = nth % value;
49 } // for loop
50 return retval;
51}
52
53long long
54CombEngine::vector2Index (CombEngine::IVec vec) const
55{
56 if (vec.size() != m_choose)
57 {
58 // we have a mismatch
59 cerr << "Error: CombEngine::vector2index: invalid vector size" << endl;
60 return -1;
61 }
62 long long retval = 0;
63 for (int loop = 0; loop < m_choose; ++loop)
64 {
65 int value = vec[0];
66 retval += (value - m_startAt) * m_decodeVec[loop];
67 _reduceVector (vec, value);
68 } // for loop
69 return retval;
70}
71
72//////////////////////////////
73// Private Member Functions //
74//////////////////////////////
75
76int
77CombEngine::_getNthComponent(int nth) const
78{
79 assert (nth < (int) m_currentVec.size());
80 int count = 0;
81 for (IVecIter iter = m_currentVec.begin();
82 iter != m_currentVec.end();
83 ++iter)
84 {
85 // are we there yet
86 if (count == nth)
87 {
88 // we're here
89 int retval = *iter;
90 m_currentVec.erase (iter);
91 return retval;
92 }
93 ++count;
94 } // for iter
95 assert(0);
96 return -1;
97}
98
99void
100CombEngine::_reduceVector (CombEngine::IVec &vec, int n) const
101{
102 // make sure we have something to work with
103 if (0 == vec.size())
104 {
105 // don't bother
106 return;
107 }
108 // remove the first element
109 IVecIter iter = vec.begin();
110 vec.erase (iter);
111 // loop through the vector and reduce all values > n
112 for (int loop = 0; loop < (int) vec.size(); ++loop)
113 {
114 if (vec[loop] > n)
115 {
116 --vec[loop];
117 }
118 } // for loop
119}
120
121void
122CombEngine::_setupDefaultVector()
123{
124 m_defaultVec.clear();
125 for (int loop = 0; loop < m_from; ++loop)
126 {
127 m_defaultVec.push_back( loop + m_startAt );
128 }
129 reset();
130}
131
132void
133CombEngine::_setupDecodingVector()
134{
135 m_decodeVec.clear();
136 for (int loop = 1; loop <= m_choose; ++loop)
137 {
138 long long value = factorialRatio (m_from - loop, m_from - m_choose);
139 m_decodeVec.push_back (value);
140 } // for loop
141}
142
143/////////////////////////////
144// Static Member Functions //
145/////////////////////////////
146
147long long
148CombEngine::factorial (int value)
149{
150 if (value <= 1)
151 {
152 return 1;
153 }
154 return value * factorial( value - 1 );
155}
156
157long long
158CombEngine::factorialRatio (int numerator, int denominator)
159{
160 // check values
161 if ((numerator < denominator) || (denominator < 0))
162 {
163 cerr << "Error: CombEngine::factorialRatio: Invalid initialization"
164 << endl;
165 assert(0);
166 }
167 if (numerator == denominator)
168 {
169 return 1;
170 }
171 long long retval = 1;
172 for (int loop = denominator + 1; loop <= numerator; ++loop)
173 {
174 retval *= loop;
175 } // for loop
176 return retval;
177}
178
179
180// friends
181ostream& operator<< (ostream& o_stream, const CombEngine &rhs)
182{
183 long long num = rhs.numCombinations();
184 int width = (int) log10 ((double) num + 1.) + 1;
185 o_stream << "combinations " << num << endl;
186 o_stream << "decode " << rhs.m_decodeVec << endl;
187 for (long long loop = 0; loop < num; ++loop)
188 {
189 CombEngine::IVec vec = rhs.combination(loop);
190 long long index = rhs.vector2Index (vec);
191 o_stream << setw(width) << loop << ") " << vec
192 << " : " << index;
193 if (loop != index)
194 {
195 o_stream << " **WARNING**";
196 }
197 o_stream << endl;
198 } // for loop
199 return o_stream;
200}
201
202ostream& operator<< (ostream& o_stream, const CombEngine::IVec &rhs)
203{
204 int size = (int) rhs.size();
205 for (int loop = 0; loop < size; ++loop)
206 {
207 o_stream << rhs[loop] << " ";
208 } // for loop
209 return o_stream;
210}
211
212ostream& operator<< (ostream& o_stream, const CombEngine::LVec &rhs)
213{
214 int size = (int) rhs.size();
215 for (int loop = 0; loop < size; ++loop)
216 {
217 o_stream << rhs[loop] << " ";
218 } // for loop
219 return o_stream;
220}

Here is the corresponding function code.