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. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 2. 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.
 *
 * SUPPORT OPEN SCIENCE!  If you use OpenMD or its source code in your
 * research, please cite the appropriate papers when you publish your
 * work.  Good starting points are:
 *                                                                      
 * [1]  Meineke, et al., J. Comp. Chem. 26, 252-271 (2005).             
 * [2]  Fennell & Gezelter, J. Chem. Phys. 124, 234104 (2006).          
 * [3]  Sun, Lin & Gezelter, J. Chem. Phys. 128, 24107 (2008).          
 * [4]  Kuang & Gezelter,  J. Chem. Phys. 133, 164101 (2010).
 * [5]  Vardeman, Stocker & Gezelter, J. Chem. Theory Comput. 7, 834 (2011).
 */
 
/**
 * @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 OpenMD {

  /**
   * @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 OpenMD
#endif //UTILS_NEXT_COMBINATION_HPP

Revision:	1665
Committed:	Tue Nov 22 20:38:56 2011 UTC (13 years, 11 months ago) by gezelter
File size:	5852 byte(s)
Log Message:	updated copyright notices
#	User	Rev	Content
1	gezelter	507	/*
2	gezelter	246	* 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	gezelter	1390	* 1. Redistributions of source code must retain the above copyright
10	gezelter	246	* notice, this list of conditions and the following disclaimer.
11			*
12	gezelter	1390	* 2. Redistributions in binary form must reproduce the above copyright
13	gezelter	246	* notice, this list of conditions and the following disclaimer in the
14			* documentation and/or other materials provided with the
15			* distribution.
16			*
17			* This software is provided "AS IS," without a warranty of any
18			* kind. All express or implied conditions, representations and
19			* warranties, including any implied warranty of merchantability,
20			* fitness for a particular purpose or non-infringement, are hereby
21			* excluded. The University of Notre Dame and its licensors shall not
22			* be liable for any damages suffered by licensee as a result of
23			* using, modifying or distributing the software or its
24			* derivatives. In no event will the University of Notre Dame or its
25			* licensors be liable for any lost revenue, profit or data, or for
26			* direct, indirect, special, consequential, incidental or punitive
27			* damages, however caused and regardless of the theory of liability,
28			* arising out of the use of or inability to use software, even if the
29			* University of Notre Dame has been advised of the possibility of
30			* such damages.
31	gezelter	1390	*
32			* SUPPORT OPEN SCIENCE! If you use OpenMD or its source code in your
33			* research, please cite the appropriate papers when you publish your
34			* work. Good starting points are:
35			*
36			* [1] Meineke, et al., J. Comp. Chem. 26, 252-271 (2005).
37			* [2] Fennell & Gezelter, J. Chem. Phys. 124, 234104 (2006).
38			* [3] Sun, Lin & Gezelter, J. Chem. Phys. 128, 24107 (2008).
39	gezelter	1665	* [4] Kuang & Gezelter, J. Chem. Phys. 133, 164101 (2010).
40			* [5] Vardeman, Stocker & Gezelter, J. Chem. Theory Comput. 7, 834 (2011).
41	tim	181	*/
42	gezelter	246
43	tim	181	/**
44	tim	187	* @file next_combination.hpp
45	tim	181	* @author tlin
46			* @date 10/27/2004
47			* @version 1.0
48			*/
49
50			#ifndef UTILS_NEXT_COMBINATION_HPP
51			#define UTILS_NEXT_COMBINATION_HPP
52
53			#include <vector>
54			#include <iterator>
55	tim	184	#include <iostream>
56	gezelter	1390	namespace OpenMD {
57	tim	181
58	gezelter	507	/**
59			* @brief STL next_permuationtation like combination sequence generator.
60			* Given the first and last iterator of a sequence, next_combination iteratively generates all
61			* possible combinations.
62			* @return if more combination is availiable, otherwise return false
63			* @param iterContainer iterator container
64			* @param first the first iterator
65			* @param last the last iterator
66			* @note first and last must be random access iterators and iterContainer must be the container of
67			* random access iterators . And all of the iteratos in iterContainer must be within the range [first, last)
68			*
69			* @code
70			* std::vector<int> iv;
71			* iv.push_back(1);
72			* iv.push_back(8);
73			* std::vector<std::vector<int>::iterator> ic;
74			* while(next_combination(ic, iv.begin(), iv.end())) {
75			* for (i = ic.begin(); i < ic.end(); ++i) {
76			* std::cout << **i << "\t";
77			* }
78			* std::cout << std::endl;
79			* }
80			* //output
81			* //1
82			* //8
83			* //1 8
84			* @endcode
85			*/
86			template<class RandomAccessIterator>
87			bool next_combination(std::vector<RandomAccessIterator>& iterContainer, RandomAccessIterator first, RandomAccessIterator last) {
88	tim	181	if (first == last) {
89	gezelter	507	return false;
90	tim	181	}
91
92	tim	182	RandomAccessIterator endIter = --last;
93	tim	371	typename std::vector<RandomAccessIterator>::iterator i = iterContainer.end();
94	tim	181
95			if (iterContainer.empty()) {
96	gezelter	507	//if sequence is empty, we insert the first iterator
97			iterContainer.insert(iterContainer.end(), first);
98			return true;
99	tim	181	} else if (*(--i) != endIter){
100	gezelter	507	//if the last iterator in iterContainer does not reaches the end, just increase its iterator by 1
101			++(*i);
102			return true;
103	tim	181	} else {// the last iterator in iterContainer does not reaches the end
104
105	gezelter	507	//starts at the end of the sequence and works its way towards the front, looking for two
106			//consecutive members of the sequence where the difference between them is greater
107			//than one. For example , if the sequence contains 1, 5, 8, 9 (total number is 10, first is 0
108			//and the last is 10 (due to STL's half open range)). At the end of while
109			//loop, j will point to 5, and i will point to 8, next combination should be 1, 6, 7, 8.
110			//If j is less than zero, it means it already reaches the last combination of current size.
111			//For instance, sequence may contain 6, 7, 8, 9 at this time, we need to increase the size
112			// of combination to 5
113			typename std::vector<RandomAccessIterator>::iterator j = i;
114			j--;
115			while( j >= iterContainer.begin() && i == j + 1){
116			i--;
117			j--;
118			};
119	tim	181
120	gezelter	507	RandomAccessIterator raIter;
121			if (j - iterContainer.begin() < 0) { //reaches the last combination of current size
122			//half open range
123			if (last - first + 1 == iterContainer.size()) {
124			//if the current size equals to total number, done
125			return false;
126			} else {
127	tim	181
128	gezelter	507	//push the first currentSize+1 element into sequence
129	tim	181
130	gezelter	507	for(i = iterContainer.begin(), raIter= first; i != iterContainer.end(); ++i, ++raIter) {
131			*i = raIter;
132			}
133			iterContainer.insert(iterContainer.end(), raIter);
134	tim	181
135	gezelter	507	return true;
136			}
137	tim	181
138	gezelter	507	} else {
139			++(*j);
140			raIter = *j;
141			for(; i != iterContainer.end(); ++i) {
142			++raIter;
143			*i = raIter;
144			}
145			return true;
146			}
147	tim	181	}
148	gezelter	507	} //end next_combination
149	tim	181
150	gezelter	1390	} //end namespace OpenMD
151	tim	181	#endif //UTILS_NEXT_COMBINATION_HPP
152