src/utils/next_combination.hpp

/*
 * Copyright (C) 2000-2004  Object Oriented Parallel Simulation Engine (OOPSE) project
 * 
 * Contact: oopse@oopse.org
 * 
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License
 * as published by the Free Software Foundation; either version 2.1
 * of the License, or (at your option) any later version.
 * All we ask is that proper credit is given for our work, which includes
 * - but is not limited to - adding the above copyright notice to the beginning
 * of your source code files, and to any copyright notice that you may distribute
 * with programs based on this work.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *
 */

/**
 * @file GenerateCombination.hpp
 * @author    tlin
 * @date  10/27/2004
 * @version 1.0
 */ 

#ifndef UTILS_NEXT_COMBINATION_HPP
#define UTILS_NEXT_COMBINATION_HPP

#include <vector>
#include <iterator>
#include <iostream>
namespace oopse {

/**
 * @fn bool next_combination(IteratorContainer<RandomAccessIterator>& iterContainer,
 *                                           RandomAccessIterator first, RandomAccessIterator last)
 * @brief STL next_permuationtation like combination sequence generator.
 * Given the first and last iterator of a sequence, next_combination iteratively generates all 
 * possible combination.
 * @return if more combination is availiable, otherwise return false
 * @param iterContainer iterator container
 * @param first the first iterator
 * @param last the last iterator
 * @note first and last must be random access iterators and iterContainer must be the container of  
 * random access iterators . And all of the iteratos in iterContainer must be within the range [first, last)
 *
 * @code
 * std::vector<int> iv;
 * iv.push_back(1);
 * iv.push_back(8);
 * std::vector<std::vector<int>::iterator> ic;
 * while(next_combination(ic, iv.begin(), iv.end())) {
 *     for (i =  ic.begin(); i < ic.end(); ++i) {
 *         std::cout << **i << "\t";
 *     }
 *     std::cout << std::endl;
 * }
 * //output
 * //1
 * //8
 * //1  8
 */
template<class RandomAccessIterator, template<typename ELEM, typename = std::allocator<ELEM> > class IteratorContainer>
bool next_combination(IteratorContainer<RandomAccessIterator>& iterContainer, RandomAccessIterator first, RandomAccessIterator last) {
    if (first == last) {
        return false;
    }
    
    RandomAccessIterator endIter = --last;
    typename IteratorContainer<RandomAccessIterator>::iterator i = iterContainer.end();
    
    if (iterContainer.empty()) {
        //if sequence is empty, we insert the first iterator
        iterContainer.insert(iterContainer.end(), first);
        return true;
    } else if (*(--i) != endIter){
        //if the last iterator in iterContainer does not reaches the end, just increment it 
        ++(*i);
        return true;
    } else {// the last iterator in iterContainer does not reaches the end

        //starts at the end of the sequence and works its way towards the front, looking for two 
        //consecutive members of the sequence where the difference between them is greater 
        //than one. For example , if the sequence contains 1, 5, 8, 9 (total number is 10, begin
        //index is 0, therefore 9 is the end index, and the current size is 4). At the end of while
        //loop, j will point to 5, and i will point to 8, next combination should be 1, 6, 7, 8.
        //If j is less than zero, it means it already reaches the last combination of current size.
        //For instance, sequence may contain 6, 7, 8, 9 at this time, we need to increase the size
        // of combination to 5
        typename IteratorContainer<RandomAccessIterator>::iterator j = i;
        j--;
        while( j >= iterContainer.begin() && *i == *j + 1){
            i--;
            j--;
        };

        RandomAccessIterator raIter;
        if (j - iterContainer.begin() < 0) { //reaches the last combination of current size
            //half open range
            if (last  - first + 1  == iterContainer.size()) {
                //if the current size equals to total number, done
                return false;
            } else {

                //push the first currentSize+1 element into sequence 
                
                for(i = iterContainer.begin(), raIter= first; i  != iterContainer.end(); ++i, ++raIter) {
                    *i = raIter;
                }    
                iterContainer.insert(iterContainer.end(), raIter);
                
                return true; 
            }
            
        } else {
            ++(*j);
            raIter = *j;
            for(; i != iterContainer.end(); ++i) {
                ++raIter;
                *i = raIter;
            }
            return true;
        }
    }
} //end next_combination

/**
 * @fn bool replaceWildCard(std::vector<std::vector<std::string>::iterator>& cont,
 *                                        std::vector<std::string>& sequence, std::vector<std::string>& result,
 *                                        const std::string& wildCard)
 * @brief iteratively replace the sequence with wild cards
 * @return true if more combination sequence is avaliable, otherwise return true
 * @param cont iterator container, if expect whole series of combination, just pass an empty iterator 
 * container. The user should not modify the iterator container
 * @param sequence the whole sequence used to generate combination
 * @param result a possible combination sequence which is set on return
 * @wildCard the wild card string. Its value is "X" by default
 * @note since next_combination never returns an empty sequence, replaceWildCard will not generate 
 * one special combination, which is n identical wild cards (n is equal to the size of the passing sequence)
 * 
 * @code
 * std::vector<std::string> sv;
 * std::vector<std::vector<std::string>::iterator> sic;
 * std::vector<std::string> resultString;
 * sv.push_back("H");
 * sv.push_back("C");
 * sv.push_back("N");

 * while (replaceWildCard(sic, sv, resultString)) {   
 *     for(std::vector<std::string>::iterator i = resultString.begin(); i != resultString.end(); ++i) {
 *         std::cout << *i << "\t";
 *     }
 *     std::cout << std::endl;
 * }
 * //output
 * //H X X
 * //X C X
 * //X X N
 * //H C X
 * //H X N
 * //X C N
 * //H C N
 @endcode
 */
bool replaceWildCard(std::vector<std::vector<std::string>::iterator>& cont,
                                             std::vector<std::string>& sequence, std::vector<std::string>& result,
                                             const std::string& wildCard = "X") {
    if (cont.size() > sequence.size()) {
        std::cerr << "the size of iterator container is greater than the size of sequence";
    }

    bool hasMoreCombination = next_combination(cont, sequence.begin(), sequence.end());
    if (hasMoreCombination) {
        result.clear();
        result.insert(result.begin(), sequence.size(), wildCard);
        std::vector<std::vector<std::string>::iterator>::iterator i;
        for ( i = cont.begin(); i != cont.end(); i++){
            result[*i - sequence.begin()] = **i;
        }
    }

     return hasMoreCombination;
    
}

} //end namespace oopse
#endif //UTILS_NEXT_COMBINATION_HPP

Revision:	185
Committed:	Thu Oct 28 21:11:12 2004 UTC (21 years ago) by tim
File size:	7718 byte(s)
Log Message:	change documentation of next_combination.hpp
#	User	Rev	Content
1	tim	181	/*
2			* Copyright (C) 2000-2004 Object Oriented Parallel Simulation Engine (OOPSE) project
3			*
4			* Contact: oopse@oopse.org
5			*
6			* This program is free software; you can redistribute it and/or
7			* modify it under the terms of the GNU Lesser General Public License
8			* as published by the Free Software Foundation; either version 2.1
9			* of the License, or (at your option) any later version.
10			* All we ask is that proper credit is given for our work, which includes
11			* - but is not limited to - adding the above copyright notice to the beginning
12			* of your source code files, and to any copyright notice that you may distribute
13			* with programs based on this work.
14			*
15			* This program is distributed in the hope that it will be useful,
16			* but WITHOUT ANY WARRANTY; without even the implied warranty of
17			* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18			* GNU Lesser General Public License for more details.
19			*
20			* You should have received a copy of the GNU Lesser General Public License
21			* along with this program; if not, write to the Free Software
22			* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
23			*
24			*/
25
26			/**
27			* @file GenerateCombination.hpp
28			* @author tlin
29			* @date 10/27/2004
30			* @version 1.0
31			*/
32
33			#ifndef UTILS_NEXT_COMBINATION_HPP
34			#define UTILS_NEXT_COMBINATION_HPP
35
36			#include <vector>
37			#include <iterator>
38	tim	184	#include <iostream>
39	tim	181	namespace oopse {
40
41			/**
42	tim	185	* @fn bool next_combination(IteratorContainer<RandomAccessIterator>& iterContainer,
43			* RandomAccessIterator first, RandomAccessIterator last)
44	tim	183	* @brief STL next_permuationtation like combination sequence generator.
45	tim	185	* Given the first and last iterator of a sequence, next_combination iteratively generates all
46			* possible combination.
47			* @return if more combination is availiable, otherwise return false
48	tim	183	* @param iterContainer iterator container
49			* @param first the first iterator
50			* @param last the last iterator
51	tim	185	* @note first and last must be random access iterators and iterContainer must be the container of
52			* random access iterators . And all of the iteratos in iterContainer must be within the range [first, last)
53	tim	183	*
54			* @code
55			* std::vector<int> iv;
56			* iv.push_back(1);
57			* iv.push_back(8);
58			* std::vector<std::vector<int>::iterator> ic;
59			* while(next_combination(ic, iv.begin(), iv.end())) {
60			* for (i = ic.begin(); i < ic.end(); ++i) {
61			* std::cout << **i << "\t";
62			* }
63			* std::cout << std::endl;
64			* }
65			* //output
66			* //1
67			* //8
68			* //1 8
69	tim	181	*/
70	tim	182	template<class RandomAccessIterator, template<typename ELEM, typename = std::allocator<ELEM> > class IteratorContainer>
71			bool next_combination(IteratorContainer<RandomAccessIterator>& iterContainer, RandomAccessIterator first, RandomAccessIterator last) {
72	tim	181	if (first == last) {
73			return false;
74			}
75
76	tim	182	RandomAccessIterator endIter = --last;
77			typename IteratorContainer<RandomAccessIterator>::iterator i = iterContainer.end();
78	tim	181
79			if (iterContainer.empty()) {
80			//if sequence is empty, we insert the first iterator
81			iterContainer.insert(iterContainer.end(), first);
82			return true;
83			} else if (*(--i) != endIter){
84			//if the last iterator in iterContainer does not reaches the end, just increment it
85			++(*i);
86			return true;
87			} else {// the last iterator in iterContainer does not reaches the end
88
89			//starts at the end of the sequence and works its way towards the front, looking for two
90			//consecutive members of the sequence where the difference between them is greater
91			//than one. For example , if the sequence contains 1, 5, 8, 9 (total number is 10, begin
92			//index is 0, therefore 9 is the end index, and the current size is 4). At the end of while
93			//loop, j will point to 5, and i will point to 8, next combination should be 1, 6, 7, 8.
94			//If j is less than zero, it means it already reaches the last combination of current size.
95			//For instance, sequence may contain 6, 7, 8, 9 at this time, we need to increase the size
96			// of combination to 5
97	tim	182	typename IteratorContainer<RandomAccessIterator>::iterator j = i;
98	tim	181	j--;
99			while( j >= iterContainer.begin() && i == j + 1){
100			i--;
101			j--;
102			};
103
104	tim	182	RandomAccessIterator raIter;
105	tim	181	if (j - iterContainer.begin() < 0) { //reaches the last combination of current size
106			//half open range
107			if (last - first + 1 == iterContainer.size()) {
108			//if the current size equals to total number, done
109			return false;
110			} else {
111
112			//push the first currentSize+1 element into sequence
113
114	tim	182	for(i = iterContainer.begin(), raIter= first; i != iterContainer.end(); ++i, ++raIter) {
115			*i = raIter;
116	tim	181	}
117	tim	182	iterContainer.insert(iterContainer.end(), raIter);
118	tim	181
119			return true;
120			}
121
122			} else {
123			++(*j);
124	tim	182	raIter = *j;
125	tim	181	for(; i != iterContainer.end(); ++i) {
126	tim	182	++raIter;
127			*i = raIter;
128	tim	181	}
129			return true;
130			}
131			}
132			} //end next_combination
133
134	tim	185	/**
135			* @fn bool replaceWildCard(std::vector<std::vector<std::string>::iterator>& cont,
136			* std::vector<std::string>& sequence, std::vector<std::string>& result,
137			* const std::string& wildCard)
138			* @brief iteratively replace the sequence with wild cards
139			* @return true if more combination sequence is avaliable, otherwise return true
140			* @param cont iterator container, if expect whole series of combination, just pass an empty iterator
141			* container. The user should not modify the iterator container
142			* @param sequence the whole sequence used to generate combination
143			* @param result a possible combination sequence which is set on return
144			* @wildCard the wild card string. Its value is "X" by default
145			* @note since next_combination never returns an empty sequence, replaceWildCard will not generate
146			* one special combination, which is n identical wild cards (n is equal to the size of the passing sequence)
147			*
148			* @code
149			* std::vector<std::string> sv;
150			* std::vector<std::vector<std::string>::iterator> sic;
151			* std::vector<std::string> resultString;
152			* sv.push_back("H");
153			* sv.push_back("C");
154			* sv.push_back("N");
155
156			* while (replaceWildCard(sic, sv, resultString)) {
157			* for(std::vector<std::string>::iterator i = resultString.begin(); i != resultString.end(); ++i) {
158			* std::cout << *i << "\t";
159			* }
160			* std::cout << std::endl;
161			* }
162			* //output
163			* //H X X
164			* //X C X
165			* //X X N
166			* //H C X
167			* //H X N
168			* //X C N
169			* //H C N
170			@endcode
171			*/
172	tim	183	bool replaceWildCard(std::vector<std::vector<std::string>::iterator>& cont,
173	tim	184	std::vector<std::string>& sequence, std::vector<std::string>& result,
174			const std::string& wildCard = "X") {
175			if (cont.size() > sequence.size()) {
176			std::cerr << "the size of iterator container is greater than the size of sequence";
177	tim	183	}
178
179			bool hasMoreCombination = next_combination(cont, sequence.begin(), sequence.end());
180			if (hasMoreCombination) {
181	tim	184	result.clear();
182			result.insert(result.begin(), sequence.size(), wildCard);
183			std::vector<std::vector<std::string>::iterator>::iterator i;
184	tim	183	for ( i = cont.begin(); i != cont.end(); i++){
185			result[i - sequence.begin()] = *i;
186	tim	184	}
187	tim	183	}
188
189			return hasMoreCombination;
190	tim	184
191	tim	183	}
192
193	tim	181	} //end namespace oopse
194			#endif //UTILS_NEXT_COMBINATION_HPP
195