1 |
< |
/* |
1 |
> |
/* |
2 |
|
* Copyright (c) 2005 The University of Notre Dame. All Rights Reserved. |
3 |
|
* |
4 |
|
* The University of Notre Dame grants you ("Licensee") a |
54 |
|
#include <iostream> |
55 |
|
namespace oopse { |
56 |
|
|
57 |
< |
/** |
58 |
< |
* @brief STL next_permuationtation like combination sequence generator. |
59 |
< |
* Given the first and last iterator of a sequence, next_combination iteratively generates all |
60 |
< |
* possible combinations. |
61 |
< |
* @return if more combination is availiable, otherwise return false |
62 |
< |
* @param iterContainer iterator container |
63 |
< |
* @param first the first iterator |
64 |
< |
* @param last the last iterator |
65 |
< |
* @note first and last must be random access iterators and iterContainer must be the container of |
66 |
< |
* random access iterators . And all of the iteratos in iterContainer must be within the range [first, last) |
67 |
< |
* |
68 |
< |
* @code |
69 |
< |
* std::vector<int> iv; |
70 |
< |
* iv.push_back(1); |
71 |
< |
* iv.push_back(8); |
72 |
< |
* std::vector<std::vector<int>::iterator> ic; |
73 |
< |
* while(next_combination(ic, iv.begin(), iv.end())) { |
74 |
< |
* for (i = ic.begin(); i < ic.end(); ++i) { |
75 |
< |
* std::cout << **i << "\t"; |
76 |
< |
* } |
77 |
< |
* std::cout << std::endl; |
78 |
< |
* } |
79 |
< |
* //output |
80 |
< |
* //1 |
81 |
< |
* //8 |
82 |
< |
* //1 8 |
83 |
< |
* @endcode |
84 |
< |
*/ |
85 |
< |
template<class RandomAccessIterator> |
86 |
< |
bool next_combination(std::vector<RandomAccessIterator>& iterContainer, RandomAccessIterator first, RandomAccessIterator last) { |
57 |
> |
/** |
58 |
> |
* @brief STL next_permuationtation like combination sequence generator. |
59 |
> |
* Given the first and last iterator of a sequence, next_combination iteratively generates all |
60 |
> |
* possible combinations. |
61 |
> |
* @return if more combination is availiable, otherwise return false |
62 |
> |
* @param iterContainer iterator container |
63 |
> |
* @param first the first iterator |
64 |
> |
* @param last the last iterator |
65 |
> |
* @note first and last must be random access iterators and iterContainer must be the container of |
66 |
> |
* random access iterators . And all of the iteratos in iterContainer must be within the range [first, last) |
67 |
> |
* |
68 |
> |
* @code |
69 |
> |
* std::vector<int> iv; |
70 |
> |
* iv.push_back(1); |
71 |
> |
* iv.push_back(8); |
72 |
> |
* std::vector<std::vector<int>::iterator> ic; |
73 |
> |
* while(next_combination(ic, iv.begin(), iv.end())) { |
74 |
> |
* for (i = ic.begin(); i < ic.end(); ++i) { |
75 |
> |
* std::cout << **i << "\t"; |
76 |
> |
* } |
77 |
> |
* std::cout << std::endl; |
78 |
> |
* } |
79 |
> |
* //output |
80 |
> |
* //1 |
81 |
> |
* //8 |
82 |
> |
* //1 8 |
83 |
> |
* @endcode |
84 |
> |
*/ |
85 |
> |
template<class RandomAccessIterator> |
86 |
> |
bool next_combination(std::vector<RandomAccessIterator>& iterContainer, RandomAccessIterator first, RandomAccessIterator last) { |
87 |
|
if (first == last) { |
88 |
< |
return false; |
88 |
> |
return false; |
89 |
|
} |
90 |
|
|
91 |
|
RandomAccessIterator endIter = --last; |
92 |
|
typename std::vector<RandomAccessIterator>::iterator i = iterContainer.end(); |
93 |
|
|
94 |
|
if (iterContainer.empty()) { |
95 |
< |
//if sequence is empty, we insert the first iterator |
96 |
< |
iterContainer.insert(iterContainer.end(), first); |
97 |
< |
return true; |
95 |
> |
//if sequence is empty, we insert the first iterator |
96 |
> |
iterContainer.insert(iterContainer.end(), first); |
97 |
> |
return true; |
98 |
|
} else if (*(--i) != endIter){ |
99 |
< |
//if the last iterator in iterContainer does not reaches the end, just increase its iterator by 1 |
100 |
< |
++(*i); |
101 |
< |
return true; |
99 |
> |
//if the last iterator in iterContainer does not reaches the end, just increase its iterator by 1 |
100 |
> |
++(*i); |
101 |
> |
return true; |
102 |
|
} else {// the last iterator in iterContainer does not reaches the end |
103 |
|
|
104 |
< |
//starts at the end of the sequence and works its way towards the front, looking for two |
105 |
< |
//consecutive members of the sequence where the difference between them is greater |
106 |
< |
//than one. For example , if the sequence contains 1, 5, 8, 9 (total number is 10, first is 0 |
107 |
< |
//and the last is 10 (due to STL's half open range)). At the end of while |
108 |
< |
//loop, j will point to 5, and i will point to 8, next combination should be 1, 6, 7, 8. |
109 |
< |
//If j is less than zero, it means it already reaches the last combination of current size. |
110 |
< |
//For instance, sequence may contain 6, 7, 8, 9 at this time, we need to increase the size |
111 |
< |
// of combination to 5 |
112 |
< |
typename std::vector<RandomAccessIterator>::iterator j = i; |
113 |
< |
j--; |
114 |
< |
while( j >= iterContainer.begin() && *i == *j + 1){ |
115 |
< |
i--; |
116 |
< |
j--; |
117 |
< |
}; |
104 |
> |
//starts at the end of the sequence and works its way towards the front, looking for two |
105 |
> |
//consecutive members of the sequence where the difference between them is greater |
106 |
> |
//than one. For example , if the sequence contains 1, 5, 8, 9 (total number is 10, first is 0 |
107 |
> |
//and the last is 10 (due to STL's half open range)). At the end of while |
108 |
> |
//loop, j will point to 5, and i will point to 8, next combination should be 1, 6, 7, 8. |
109 |
> |
//If j is less than zero, it means it already reaches the last combination of current size. |
110 |
> |
//For instance, sequence may contain 6, 7, 8, 9 at this time, we need to increase the size |
111 |
> |
// of combination to 5 |
112 |
> |
typename std::vector<RandomAccessIterator>::iterator j = i; |
113 |
> |
j--; |
114 |
> |
while( j >= iterContainer.begin() && *i == *j + 1){ |
115 |
> |
i--; |
116 |
> |
j--; |
117 |
> |
}; |
118 |
|
|
119 |
< |
RandomAccessIterator raIter; |
120 |
< |
if (j - iterContainer.begin() < 0) { //reaches the last combination of current size |
121 |
< |
//half open range |
122 |
< |
if (last - first + 1 == iterContainer.size()) { |
123 |
< |
//if the current size equals to total number, done |
124 |
< |
return false; |
125 |
< |
} else { |
119 |
> |
RandomAccessIterator raIter; |
120 |
> |
if (j - iterContainer.begin() < 0) { //reaches the last combination of current size |
121 |
> |
//half open range |
122 |
> |
if (last - first + 1 == iterContainer.size()) { |
123 |
> |
//if the current size equals to total number, done |
124 |
> |
return false; |
125 |
> |
} else { |
126 |
|
|
127 |
< |
//push the first currentSize+1 element into sequence |
127 |
> |
//push the first currentSize+1 element into sequence |
128 |
|
|
129 |
< |
for(i = iterContainer.begin(), raIter= first; i != iterContainer.end(); ++i, ++raIter) { |
130 |
< |
*i = raIter; |
131 |
< |
} |
132 |
< |
iterContainer.insert(iterContainer.end(), raIter); |
129 |
> |
for(i = iterContainer.begin(), raIter= first; i != iterContainer.end(); ++i, ++raIter) { |
130 |
> |
*i = raIter; |
131 |
> |
} |
132 |
> |
iterContainer.insert(iterContainer.end(), raIter); |
133 |
|
|
134 |
< |
return true; |
135 |
< |
} |
134 |
> |
return true; |
135 |
> |
} |
136 |
|
|
137 |
< |
} else { |
138 |
< |
++(*j); |
139 |
< |
raIter = *j; |
140 |
< |
for(; i != iterContainer.end(); ++i) { |
141 |
< |
++raIter; |
142 |
< |
*i = raIter; |
143 |
< |
} |
144 |
< |
return true; |
145 |
< |
} |
137 |
> |
} else { |
138 |
> |
++(*j); |
139 |
> |
raIter = *j; |
140 |
> |
for(; i != iterContainer.end(); ++i) { |
141 |
> |
++raIter; |
142 |
> |
*i = raIter; |
143 |
> |
} |
144 |
> |
return true; |
145 |
> |
} |
146 |
|
} |
147 |
< |
} //end next_combination |
147 |
> |
} //end next_combination |
148 |
|
|
149 |
|
} //end namespace oopse |
150 |
|
#endif //UTILS_NEXT_COMBINATION_HPP |