src/utils/next_combination.hpp

 /*
 * Copyright (c) 2005 The University of Notre Dame. All Rights Reserved.
 *
 * The University of Notre Dame grants you ("Licensee") a
 * non-exclusive, royalty free, license to use, modify and
 * redistribute this software in source and binary code form, provided
 * that the following conditions are met:
 *
 * 1. Acknowledgement of the program authors must be made in any
 *    publication of scientific results based in part on use of the
 *    program.  An acceptable form of acknowledgement is citation of
 *    the article in which the program was described (Matthew
 *    A. Meineke, Charles F. Vardeman II, Teng Lin, Christopher
 *    J. Fennell and J. Daniel Gezelter, "OOPSE: An Object-Oriented
 *    Parallel Simulation Engine for Molecular Dynamics,"
 *    J. Comput. Chem. 26, pp. 252-271 (2005))
 *
 * 2. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 3. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the
 *    distribution.
 *
 * This software is provided "AS IS," without a warranty of any
 * kind. All express or implied conditions, representations and
 * warranties, including any implied warranty of merchantability,
 * fitness for a particular purpose or non-infringement, are hereby
 * excluded.  The University of Notre Dame and its licensors shall not
 * be liable for any damages suffered by licensee as a result of
 * using, modifying or distributing the software or its
 * derivatives. In no event will the University of Notre Dame or its
 * licensors be liable for any lost revenue, profit or data, or for
 * direct, indirect, special, consequential, incidental or punitive
 * damages, however caused and regardless of the theory of liability,
 * arising out of the use of or inability to use software, even if the
 * University of Notre Dame has been advised of the possibility of
 * such damages.
 */
 
/**
 * @file next_combination.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 {

/**
 * @brief STL next_permuationtation like combination sequence generator.
 * Given the first and last iterator of a sequence, next_combination iteratively generates all 
 * possible combinations.
 * @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
 * @endcode
 */
template<class RandomAccessIterator>
bool next_combination(std::vector<RandomAccessIterator>& iterContainer, RandomAccessIterator first, RandomAccessIterator last) {
    if (first == last) {
        return false;
    }
    
    RandomAccessIterator endIter = --last;
    typename std::vector<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 increase its iterator by 1 
        ++(*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, first is 0
        //and the last is 10 (due to STL's half open range)). 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 std::vector<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

} //end namespace oopse
#endif //UTILS_NEXT_COMBINATION_HPP

Revision:	371
Committed:	Mon Feb 21 15:22:56 2005 UTC (20 years, 2 months ago) by tim
Original Path:	*trunk/src/utils/next_combination.hpp*
File size:	5981 byte(s)
Log Message:	fix for compilation on the Sun
#	User	Rev	Content
1	gezelter	246	/*
2			* Copyright (c) 2005 The University of Notre Dame. All Rights Reserved.
3	tim	181	*
4	gezelter	246	* The University of Notre Dame grants you ("Licensee") a
5			* non-exclusive, royalty free, license to use, modify and
6			* redistribute this software in source and binary code form, provided
7			* that the following conditions are met:
8			*
9			* 1. Acknowledgement of the program authors must be made in any
10			* publication of scientific results based in part on use of the
11			* program. An acceptable form of acknowledgement is citation of
12			* the article in which the program was described (Matthew
13			* A. Meineke, Charles F. Vardeman II, Teng Lin, Christopher
14			* J. Fennell and J. Daniel Gezelter, "OOPSE: An Object-Oriented
15			* Parallel Simulation Engine for Molecular Dynamics,"
16			* J. Comput. Chem. 26, pp. 252-271 (2005))
17			*
18			* 2. Redistributions of source code must retain the above copyright
19			* notice, this list of conditions and the following disclaimer.
20			*
21			* 3. Redistributions in binary form must reproduce the above copyright
22			* notice, this list of conditions and the following disclaimer in the
23			* documentation and/or other materials provided with the
24			* distribution.
25			*
26			* This software is provided "AS IS," without a warranty of any
27			* kind. All express or implied conditions, representations and
28			* warranties, including any implied warranty of merchantability,
29			* fitness for a particular purpose or non-infringement, are hereby
30			* excluded. The University of Notre Dame and its licensors shall not
31			* be liable for any damages suffered by licensee as a result of
32			* using, modifying or distributing the software or its
33			* derivatives. In no event will the University of Notre Dame or its
34			* licensors be liable for any lost revenue, profit or data, or for
35			* direct, indirect, special, consequential, incidental or punitive
36			* damages, however caused and regardless of the theory of liability,
37			* arising out of the use of or inability to use software, even if the
38			* University of Notre Dame has been advised of the possibility of
39			* such damages.
40	tim	181	*/
41	gezelter	246
42	tim	181	/**
43	tim	187	* @file next_combination.hpp
44	tim	181	* @author tlin
45			* @date 10/27/2004
46			* @version 1.0
47			*/
48
49			#ifndef UTILS_NEXT_COMBINATION_HPP
50			#define UTILS_NEXT_COMBINATION_HPP
51
52			#include <vector>
53			#include <iterator>
54	tim	184	#include <iostream>
55	tim	181	namespace oopse {
56
57			/**
58	tim	183	* @brief STL next_permuationtation like combination sequence generator.
59	tim	185	* Given the first and last iterator of a sequence, next_combination iteratively generates all
60	tim	186	* possible combinations.
61	tim	185	* @return if more combination is availiable, otherwise return false
62	tim	183	* @param iterContainer iterator container
63			* @param first the first iterator
64			* @param last the last iterator
65	tim	185	* @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	tim	183	*
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	tim	186	* @endcode
84	tim	181	*/
85	tim	371	template<class RandomAccessIterator>
86			bool next_combination(std::vector<RandomAccessIterator>& iterContainer, RandomAccessIterator first, RandomAccessIterator last) {
87	tim	181	if (first == last) {
88			return false;
89			}
90
91	tim	182	RandomAccessIterator endIter = --last;
92	tim	371	typename std::vector<RandomAccessIterator>::iterator i = iterContainer.end();
93	tim	181
94			if (iterContainer.empty()) {
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	tim	187	//if the last iterator in iterContainer does not reaches the end, just increase its iterator by 1
100	tim	181	++(*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	tim	187	//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	tim	181	//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	tim	371	typename std::vector<RandomAccessIterator>::iterator j = i;
113	tim	181	j--;
114			while( j >= iterContainer.begin() && i == j + 1){
115			i--;
116			j--;
117			};
118
119	tim	182	RandomAccessIterator raIter;
120	tim	181	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
128
129	tim	182	for(i = iterContainer.begin(), raIter= first; i != iterContainer.end(); ++i, ++raIter) {
130			*i = raIter;
131	tim	181	}
132	tim	182	iterContainer.insert(iterContainer.end(), raIter);
133	tim	181
134			return true;
135			}
136
137			} else {
138			++(*j);
139	tim	182	raIter = *j;
140	tim	181	for(; i != iterContainer.end(); ++i) {
141	tim	182	++raIter;
142			*i = raIter;
143	tim	181	}
144			return true;
145			}
146			}
147			} //end next_combination
148
149			} //end namespace oopse
150			#endif //UTILS_NEXT_COMBINATION_HPP
151