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 371 by tim, Mon Feb 21 15:22:56 2005 UTC vs.
Revision 1442 by gezelter, Mon May 10 17:28:26 2010 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, 24107 (2008).
39	+	* [4]  Vardeman & Gezelter, in progress (2009).
40		*/
41
42		/**
#	Line 52 | Line 52
52		#include <vector>
53		#include <iterator>
54		#include <iostream>
55	<	namespace oopse {
55	>	namespace OpenMD {
56
57	<	/**
58	<	* @brief STL next_permuationtation like combination sequence generator.
59	<	* Given the first and last iterator of a sequence, next_combination iteratively generates all
60	<	* possible combinations.
61	<	* @return if more combination is availiable, otherwise return false
62	<	* @param iterContainer iterator container
63	<	* @param first the first iterator
64	<	* @param last the last iterator
65	<	* @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	<	*
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	<	* @endcode
84	<	*/
85	<	template<class RandomAccessIterator>
86	<	bool next_combination(std::vector<RandomAccessIterator>& iterContainer, RandomAccessIterator first, RandomAccessIterator last) {
57	>	/**
58	>	* @brief STL next_permuationtation like combination sequence generator.
59	>	* Given the first and last iterator of a sequence, next_combination iteratively generates all
60	>	* possible combinations.
61	>	* @return if more combination is availiable, otherwise return false
62	>	* @param iterContainer iterator container
63	>	* @param first the first iterator
64	>	* @param last the last iterator
65	>	* @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	>	*
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	>	* @endcode
84	>	*/
85	>	template<class RandomAccessIterator>
86	>	bool next_combination(std::vector<RandomAccessIterator>& iterContainer, RandomAccessIterator first, RandomAccessIterator last) {
87		if (first == last) {
88	<	return false;
88	>	return false;
89		}
90
91		RandomAccessIterator endIter = --last;
92		typename std::vector<RandomAccessIterator>::iterator i = iterContainer.end();
93
94		if (iterContainer.empty()) {
95	<	//if sequence is empty, we insert the first iterator
96	<	iterContainer.insert(iterContainer.end(), first);
97	<	return true;
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	<	//if the last iterator in iterContainer does not reaches the end, just increase its iterator by 1
100	<	++(*i);
101	<	return true;
99	>	//if the last iterator in iterContainer does not reaches the end, just increase its iterator by 1
100	>	++(*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	<	//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	<	//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	<	typename std::vector<RandomAccessIterator>::iterator j = i;
113	<	j--;
114	<	while( j >= iterContainer.begin() && *i == *j + 1){
115	<	i--;
116	<	j--;
117	<	};
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	>	//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	>	//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	>	typename std::vector<RandomAccessIterator>::iterator j = i;
113	>	j--;
114	>	while( j >= iterContainer.begin() && *i == *j + 1){
115	>	i--;
116	>	j--;
117	>	};
118
119	<	RandomAccessIterator raIter;
120	<	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 {
119	>	RandomAccessIterator raIter;
120	>	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
127	>	//push the first currentSize+1 element into sequence
128
129	<	for(i = iterContainer.begin(), raIter= first; i  != iterContainer.end(); ++i, ++raIter) {
130	<	*i = raIter;
131	<	}
132	<	iterContainer.insert(iterContainer.end(), raIter);
129	>	for(i = iterContainer.begin(), raIter= first; i  != iterContainer.end(); ++i, ++raIter) {
130	>	*i = raIter;
131	>	}
132	>	iterContainer.insert(iterContainer.end(), raIter);
133
134	<	return true;
135	<	}
134	>	return true;
135	>	}
136
137	<	} else {
138	<	++(*j);
139	<	raIter = *j;
140	<	for(; i != iterContainer.end(); ++i) {
141	<	++raIter;
142	<	*i = raIter;
143	<	}
144	<	return true;
145	<	}
137	>	} else {
138	>	++(*j);
139	>	raIter = *j;
140	>	for(; i != iterContainer.end(); ++i) {
141	>	++raIter;
142	>	*i = raIter;
143	>	}
144	>	return true;
145	>	}
146		}
147	<	} //end next_combination
147	>	} //end next_combination
148
149	<	} //end namespace oopse
149	>	} //end namespace OpenMD
150		#endif //UTILS_NEXT_COMBINATION_HPP
151

Comparing trunk/src/utils/next_combination.hpp (property svn:keywords):
Revision 371 by tim, Mon Feb 21 15:22:56 2005 UTC vs.
Revision 1442 by gezelter, Mon May 10 17:28:26 2010 UTC

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

Diff Legend

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