| 1 |
< |
/* |
| 2 |
< |
* Copyright (C) 2000-2004 Object Oriented Parallel Simulation Engine (OOPSE) project |
| 3 |
< |
* |
| 4 |
< |
* Contact: oopse@oopse.org |
| 5 |
< |
* |
| 6 |
< |
* This program is free software; you can redistribute it and/or |
| 7 |
< |
* modify it under the terms of the GNU Lesser General Public License |
| 8 |
< |
* as published by the Free Software Foundation; either version 2.1 |
| 9 |
< |
* of the License, or (at your option) any later version. |
| 10 |
< |
* All we ask is that proper credit is given for our work, which includes |
| 11 |
< |
* - but is not limited to - adding the above copyright notice to the beginning |
| 12 |
< |
* of your source code files, and to any copyright notice that you may distribute |
| 13 |
< |
* with programs based on this work. |
| 14 |
< |
* |
| 15 |
< |
* This program is distributed in the hope that it will be useful, |
| 16 |
< |
* but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 17 |
< |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 18 |
< |
* GNU Lesser General Public License for more details. |
| 19 |
< |
* |
| 20 |
< |
* You should have received a copy of the GNU Lesser General Public License |
| 21 |
< |
* along with this program; if not, write to the Free Software |
| 22 |
< |
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. |
| 1 |
> |
/* |
| 2 |
> |
* Copyright (c) 2005 The University of Notre Dame. All Rights Reserved. |
| 3 |
|
* |
| 4 |
+ |
* 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 |
|
*/ |
| 41 |
< |
|
| 41 |
> |
|
| 42 |
|
/** |
| 43 |
< |
* @file GenerateCombination.hpp |
| 43 |
> |
* @file next_combination.hpp |
| 44 |
|
* @author tlin |
| 45 |
|
* @date 10/27/2004 |
| 46 |
|
* @version 1.0 |
| 51 |
|
|
| 52 |
|
#include <vector> |
| 53 |
|
#include <iterator> |
| 54 |
< |
|
| 54 |
> |
#include <iostream> |
| 55 |
|
namespace oopse { |
| 56 |
|
|
| 57 |
|
/** |
| 58 |
< |
* STL next_permuationtation like combination sequence generator |
| 59 |
< |
* |
| 60 |
< |
* <p> Preconditions: </p> |
| 61 |
< |
* |
| 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, template<typename ELEM, typename = std::allocator<ELEM> > class IteratorContainer> |
| 86 |
|
bool next_combination(IteratorContainer<RandomAccessIterator>& iterContainer, RandomAccessIterator first, RandomAccessIterator last) { |
| 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 increment it |
| 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, begin |
| 107 |
< |
//index is 0, therefore 9 is the end index, and the current size is 4). At the end of while |
| 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 |
