Hide
Know what you're getting – Unlike many sites, all our code is clearly licensed. Join Siafoo Now or Learn More

combEngine.h Atom Feed 0

In Brief This is the header for the combinatorics engine that will index x choose k.
# 's
  1// -*- C++ -*-
2
3#ifndef CombEngine_H
4#define CombEngine_H
5
6#include <vector>
7
8class CombEngine
9{
10 public:
11 //////////////////////
12 // Public Constants //
13 //////////////////////
14 typedef std::vector< int > IVec;
15 typedef std::vector< long long > LVec;
16 typedef IVec::iterator IVecIter;
17 typedef LVec::iterator LVecIter;
18
19 /////////////
20 // friends //
21 /////////////
22 // tells particle data how to print itself out
23 friend std::ostream& operator<< (std::ostream& o_stream,
24 const CombEngine &rhs);
25
26 //////////////////////////
27 // _ //
28 // |\/| |_ //
29 // | |EMBER | UNCTIONS //
30 // //
31 //////////////////////////
32
33 /////////////////////////////////
34 // Constructors and Destructor //
35 /////////////////////////////////
36 CombEngine(int from, int choose, int startAt = 0);
37
38 ////////////////
39 // One Liners //
40 ////////////////
41 void setStartAt (int startAt)
42 { m_startAt = startAt; _setupDefaultVector(); }
43
44 void reset() const { m_currentVec = m_defaultVec; }
45
46 // return the number of possible permutations
47 long long numCombinations() const { return m_combinations; }
48 long long numPermutations() const { return m_combinations; }
49
50 //////////////////////////////
51 // Regular Member Functions //
52 //////////////////////////////
53
54 // sets from and choose
55 void setFromAndChoose (int from, int choose);
56
57 // returns the IVec describing the nth combination
58 // nth goes from 0..numCombinations - 1;
59 IVec combination (long long nth) const;
60
61 // Given a vector, return the unique index
62 long long vector2Index (IVec vec) const;
63
64 /////////////////////////////
65 // Static Member Functions //
66 /////////////////////////////
67 // factorial function
68 static long long factorial (int value);
69
70 // factorial ratio function
71 static long long factorialRatio (int numerator, int denominator);
72
73
74 protected:
75 /////////////////////////
76 // Protected Constants //
77 /////////////////////////
78
79 ///////////////////////////
80 // Protected Member Data //
81 ///////////////////////////
82
83 private:
84 //////////////////////////////
85 // Private Member Functions //
86 //////////////////////////////
87
88 // sets up the default vector
89 void _setupDefaultVector();
90
91 // sets up the decoding vector
92 void _setupDecodingVector();
93
94 // remove the first entry and reduce all members greater than N
95 void _reduceVector (IVec &vec, int n) const;
96
97 // get the nth component out of the current vector
98 int _getNthComponent (int nth) const;
99
100
101 ///////////////////////
102 // Private Constants //
103 ///////////////////////
104
105 /////////////////////////
106 // Private Member Data //
107 /////////////////////////
108
109 IVec m_defaultVec;
110 mutable IVec m_currentVec;
111 LVec m_decodeVec;
112 int m_from;
113 int m_choose;
114 int m_startAt;
115 long long m_combinations;
116};
117
118std::ostream& operator<< (std::ostream& o_stream,
119 const CombEngine::IVec &rhs);
120
121std::ostream& operator<< (std::ostream& o_stream,
122 const CombEngine::LVec &rhs);
123
124#endif // CombEngine_H

This is the header for the combinatorics engine that will index x choose k.