OpenMD 3.0
Molecular Dynamics in the Open
Loading...
Searching...
No Matches
next_combination.hpp
Go to the documentation of this file.
1/*
2 * Copyright (c) 2004-present, The University of Notre Dame. All rights
3 * reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 *
8 * 1. Redistributions of source code must retain the above copyright notice,
9 * this list of conditions and the following disclaimer.
10 *
11 * 2. Redistributions in binary form must reproduce the above copyright notice,
12 * this list of conditions and the following disclaimer in the documentation
13 * and/or other materials provided with the distribution.
14 *
15 * 3. Neither the name of the copyright holder nor the names of its
16 * contributors may be used to endorse or promote products derived from
17 * this software without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
23 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
30 *
31 * SUPPORT OPEN SCIENCE! If you use OpenMD or its source code in your
32 * research, please cite the appropriate papers when you publish your
33 * work. Good starting points are:
34 *
35 * [1] Meineke, et al., J. Comp. Chem. 26, 252-271 (2005).
36 * [2] Fennell & Gezelter, J. Chem. Phys. 124, 234104 (2006).
37 * [3] Sun, Lin & Gezelter, J. Chem. Phys. 128, 234107 (2008).
38 * [4] Vardeman, Stocker & Gezelter, J. Chem. Theory Comput. 7, 834 (2011).
39 * [5] Kuang & Gezelter, Mol. Phys., 110, 691-701 (2012).
40 * [6] Lamichhane, Gezelter & Newman, J. Chem. Phys. 141, 134109 (2014).
41 * [7] Lamichhane, Newman & Gezelter, J. Chem. Phys. 141, 134110 (2014).
42 * [8] Bhattarai, Newman & Gezelter, Phys. Rev. B 99, 094106 (2019).
43 */
44
45/**
46 * @file next_combination.hpp
47 * @author tlin
48 * @date 10/27/2004
49 * @version 1.0
50 */
51
52#ifndef UTILS_NEXT_COMBINATION_HPP
53#define UTILS_NEXT_COMBINATION_HPP
54
55#include <iostream>
56#include <iterator>
57#include <vector>
58
59namespace OpenMD {
60
61 /**
62 * @brief STL next_permuation-like combination sequence generator.
63 * Given the first and last iterator of a sequence, next_combination
64 * iteratively generates all possible combinations.
65 * @return if more combination is availiable, otherwise return false
66 * @param iterContainer iterator container
67 * @param first the first iterator
68 * @param last the last iterator
69 * @note first and last must be random access iterators and iterContainer must
70 * be the container of random access iterators . And all of the iteratos in
71 * iterContainer must be within the range [first, last)
72 *
73 * @code
74 * std::vector<int> iv;
75 * iv.push_back(1);
76 * iv.push_back(8);
77 * std::vector<std::vector<int>::iterator> ic;
78 * while(next_combination(ic, iv.begin(), iv.end())) {
79 * for (i = ic.begin(); i < ic.end(); ++i) {
80 * std::cout << **i << "\t";
81 * }
82 * std::cout << std::endl;
83 * }
84 * //output
85 * //1
86 * //8
87 * //1 8
88 * @endcode
89 */
90 template<class RandomAccessIterator>
91 bool next_combination(std::vector<RandomAccessIterator>& iterContainer,
92 RandomAccessIterator first, RandomAccessIterator last) {
93 if (first == last) { return false; }
94
95 RandomAccessIterator endIter = --last;
96 typename std::vector<RandomAccessIterator>::iterator i =
97 iterContainer.end();
98
99 if (iterContainer.empty()) {
100 // if sequence is empty, we insert the first iterator
101 iterContainer.insert(iterContainer.end(), first);
102 return true;
103 } else if (*(--i) != endIter) {
104 // if the last iterator in iterContainer does not reaches the end, just
105 // increase its iterator by 1
106 ++(*i);
107 return true;
108 } else { // the last iterator in iterContainer does not reaches the end
109
110 // starts at the end of the sequence and works its way towards the front,
111 // looking for two consecutive members of the sequence where the
112 // difference between them is greater than one. For example , if the
113 // sequence contains 1, 5, 8, 9 (total number is 10, first is 0 and the
114 // last is 10 (due to STL's half open range)). At the end of while loop, j
115 // will point to 5, and i will point to 8, next combination should be 1,
116 // 6, 7, 8. If j is less than zero, it means it already reaches the last
117 // combination of current size. For instance, sequence may contain 6, 7,
118 // 8, 9 at this time, we need to increase the size of combination to 5
119 typename std::vector<RandomAccessIterator>::iterator j = i;
120 --j;
121 while (j >= iterContainer.begin() && *i == *j + 1) {
122 --i;
123 --j;
124 };
125
126 RandomAccessIterator raIter;
127 if (j - iterContainer.begin() <
128 0) { // reaches the last combination of current size
129 // half open range
130 if (last - first + 1 == int(iterContainer.size())) {
131 // if the current size equals to total number, done
132 return false;
133 } else {
134 // push the first currentSize+1 element into sequence
135
136 for (i = iterContainer.begin(), raIter = first;
137 i != iterContainer.end(); ++i, ++raIter) {
138 *i = raIter;
139 }
140 iterContainer.insert(iterContainer.end(), raIter);
141
142 return true;
143 }
144
145 } else {
146 ++(*j);
147 raIter = *j;
148 for (; i != iterContainer.end(); ++i) {
149 ++raIter;
150 *i = raIter;
151 }
152 return true;
153 }
154 }
155 } // end next_combination
156
157} // namespace OpenMD
158
159#endif // UTILS_NEXT_COMBINATION_HPP
This basic Periodic Table class was originally taken from the data.cpp file in OpenBabel.
bool next_combination(std::vector< RandomAccessIterator > &iterContainer, RandomAccessIterator first, RandomAccessIterator last)
STL next_permuation-like combination sequence generator.