24 |
|
*/ |
25 |
|
|
26 |
|
/** |
27 |
< |
* @file GenerateCombination.hpp |
27 |
> |
* @file next_combination.hpp |
28 |
|
* @author tlin |
29 |
|
* @date 10/27/2004 |
30 |
|
* @version 1.0 |
35 |
|
|
36 |
|
#include <vector> |
37 |
|
#include <iterator> |
38 |
< |
|
38 |
> |
#include <iostream> |
39 |
|
namespace oopse { |
40 |
|
|
41 |
|
/** |
42 |
– |
* @fn bool next_combination(IteratorContainer<RandomAccessIterator>& iterContainer, RandomAccessIterator first, RandomAccessIterator last) |
42 |
|
* @brief STL next_permuationtation like combination sequence generator. |
43 |
< |
* Given the first and last iterator of a sequence, next_combination iteratively generates all possible combination. |
43 |
> |
* Given the first and last iterator of a sequence, next_combination iteratively generates all |
44 |
> |
* possible combinations. |
45 |
> |
* @return if more combination is availiable, otherwise return false |
46 |
|
* @param iterContainer iterator container |
47 |
|
* @param first the first iterator |
48 |
|
* @param last the last iterator |
49 |
< |
* @note first and last must be random access iterators and iterContainer must be the container which |
50 |
< |
* element is iterator. And all of the iteratos in iterContainer must be within the range [first, last) |
49 |
> |
* @note first and last must be random access iterators and iterContainer must be the container of |
50 |
> |
* random access iterators . And all of the iteratos in iterContainer must be within the range [first, last) |
51 |
|
* |
52 |
|
* @code |
53 |
|
* std::vector<int> iv; |
64 |
|
* //1 |
65 |
|
* //8 |
66 |
|
* //1 8 |
67 |
+ |
* @endcode |
68 |
|
*/ |
69 |
|
template<class RandomAccessIterator, template<typename ELEM, typename = std::allocator<ELEM> > class IteratorContainer> |
70 |
|
bool next_combination(IteratorContainer<RandomAccessIterator>& iterContainer, RandomAccessIterator first, RandomAccessIterator last) { |
80 |
|
iterContainer.insert(iterContainer.end(), first); |
81 |
|
return true; |
82 |
|
} else if (*(--i) != endIter){ |
83 |
< |
//if the last iterator in iterContainer does not reaches the end, just increment it |
83 |
> |
//if the last iterator in iterContainer does not reaches the end, just increase its iterator by 1 |
84 |
|
++(*i); |
85 |
|
return true; |
86 |
|
} else {// the last iterator in iterContainer does not reaches the end |
87 |
|
|
88 |
|
//starts at the end of the sequence and works its way towards the front, looking for two |
89 |
|
//consecutive members of the sequence where the difference between them is greater |
90 |
< |
//than one. For example , if the sequence contains 1, 5, 8, 9 (total number is 10, begin |
91 |
< |
//index is 0, therefore 9 is the end index, and the current size is 4). At the end of while |
90 |
> |
//than one. For example , if the sequence contains 1, 5, 8, 9 (total number is 10, first is 0 |
91 |
> |
//and the last is 10 (due to STL's half open range)). At the end of while |
92 |
|
//loop, j will point to 5, and i will point to 8, next combination should be 1, 6, 7, 8. |
93 |
|
//If j is less than zero, it means it already reaches the last combination of current size. |
94 |
|
//For instance, sequence may contain 6, 7, 8, 9 at this time, we need to increase the size |
130 |
|
} |
131 |
|
} //end next_combination |
132 |
|
|
131 |
– |
bool replaceWildCard(std::vector<std::vector<std::string>::iterator>& cont, |
132 |
– |
std::vector<std::string> sequence, std::vector<std::string> result |
133 |
– |
std::string& wildCard = "X") { |
134 |
– |
if (cont.size() > sequnce.size()) { |
135 |
– |
std::cerr << "the size of iterator container is greater than the size of sequence" |
136 |
– |
} |
137 |
– |
|
138 |
– |
bool hasMoreCombination = next_combination(cont, sequence.begin(), sequence.end()); |
139 |
– |
if (hasMoreCombination) { |
140 |
– |
result.resize(sequence.size()); |
141 |
– |
result.insert(result.end(), sequence.size(), wildCard); |
142 |
– |
for ( i = cont.begin(); i != cont.end(); i++){ |
143 |
– |
result[*i - sequence.begin()] = **i; |
144 |
– |
} |
145 |
– |
|
146 |
– |
return hasMoreCombination; |
147 |
– |
} |
148 |
– |
|
133 |
|
} //end namespace oopse |
134 |
|
#endif //UTILS_NEXT_COMBINATION_HPP |
135 |
|
|