License Public Domain
Lines 202
Included in this Library
Permissions
Viewable by Everyone
Editable by All Siafoo Users
Hide
Easily highlight source code for your blog with our Syntax Highlighter. 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.