ViewVC Help

View File | Revision Log | Show Annotations | View Changeset | Root Listing

root/OpenMD/trunk/src/utils/next_combination.hpp

Comparing trunk/src/utils/next_combination.hpp (file contents):
Revision 246 by gezelter, Wed Jan 12 22:41:40 2005 UTC vs.
Revision 1879 by gezelter, Sun Jun 16 15:15:42 2013 UTC

#	Line 1 | Line 1
1	<	/*
1	>	/*
2		* Copyright (c) 2005 The University of Notre Dame. All Rights Reserved.
3		*
4		* The University of Notre Dame grants you ("Licensee") a
#	Line 6 | Line 6
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
9	>	* 1. Redistributions of source code must retain the above copyright
10		*    notice, this list of conditions and the following disclaimer.
11		*
12	<	* 3. Redistributions in binary form must reproduce the above copyright
12	>	* 2. Redistributions in binary form must reproduce the above copyright
13		*    notice, this list of conditions and the following disclaimer in the
14		*    documentation and/or other materials provided with the
15		*    distribution.
#	Line 37 | Line 28
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	+	*
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, 234107 (2008).
39	+	* [4]  Kuang & Gezelter,  J. Chem. Phys. 133, 164101 (2010).
40	+	* [5]  Vardeman, Stocker & Gezelter, J. Chem. Theory Comput. 7, 834 (2011).
41		*/
42
43		/**
#	Line 52 | Line 53
53		#include <vector>
54		#include <iterator>
55		#include <iostream>
56	<	namespace oopse {
56	>	namespace OpenMD {
57
58	<	/**
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, template<typename ELEM, typename = std::allocator<ELEM> > class IteratorContainer>
87	<	bool next_combination(IteratorContainer<RandomAccessIterator>& iterContainer, RandomAccessIterator first, RandomAccessIterator last) {
58	>	/**
59	>	* @brief STL next_permuation-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		if (first == last) {
89	<	return false;
89	>	return false;
90		}
91
92		RandomAccessIterator endIter = --last;
93	<	typename IteratorContainer<RandomAccessIterator>::iterator i = iterContainer.end();
93	>	typename std::vector<RandomAccessIterator>::iterator i = iterContainer.end();
94
95		if (iterContainer.empty()) {
96	<	//if sequence is empty, we insert the first iterator
97	<	iterContainer.insert(iterContainer.end(), first);
98	<	return true;
96	>	//if sequence is empty, we insert the first iterator
97	>	iterContainer.insert(iterContainer.end(), first);
98	>	return true;
99		} else if (*(--i) != endIter){
100	<	//if the last iterator in iterContainer does not reaches the end, just increase its iterator by 1
101	<	++(*i);
102	<	return true;
100	>	//if the last iterator in iterContainer does not reaches the end, just increase its iterator by 1
101	>	++(*i);
102	>	return true;
103		} else {// the last iterator in iterContainer does not reaches the end
104
105	<	//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 IteratorContainer<RandomAccessIterator>::iterator j = i;
114	<	j--;
115	<	while( j >= iterContainer.begin() && *i == *j + 1){
116	<	i--;
117	<	j--;
118	<	};
105	>	//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
120	<	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 {
120	>	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
128	<	//push the first currentSize+1 element into sequence
128	>	//push the first currentSize+1 element into sequence
129
130	<	for(i = iterContainer.begin(), raIter= first; i  != iterContainer.end(); ++i, ++raIter) {
131	<	*i = raIter;
132	<	}
133	<	iterContainer.insert(iterContainer.end(), raIter);
130	>	for(i = iterContainer.begin(), raIter= first; i  != iterContainer.end(); ++i, ++raIter) {
131	>	*i = raIter;
132	>	}
133	>	iterContainer.insert(iterContainer.end(), raIter);
134
135	<	return true;
136	<	}
135	>	return true;
136	>	}
137
138	<	} else {
139	<	++(*j);
140	<	raIter = *j;
141	<	for(; i != iterContainer.end(); ++i) {
142	<	++raIter;
143	<	*i = raIter;
144	<	}
145	<	return true;
146	<	}
138	>	} else {
139	>	++(*j);
140	>	raIter = *j;
141	>	for(; i != iterContainer.end(); ++i) {
142	>	++raIter;
143	>	*i = raIter;
144	>	}
145	>	return true;
146	>	}
147		}
148	<	} //end next_combination
148	>	} //end next_combination
149
150	<	} //end namespace oopse
150	>	} //end namespace OpenMD
151		#endif //UTILS_NEXT_COMBINATION_HPP
152

Comparing trunk/src/utils/next_combination.hpp (property svn:keywords):
Revision 246 by gezelter, Wed Jan 12 22:41:40 2005 UTC vs.
Revision 1879 by gezelter, Sun Jun 16 15:15:42 2013 UTC

#	Line 0 | Line 1
1	+	Author Id Revision Date

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines