Code-Eli  0.3.6
combination.hpp
Go to the documentation of this file.
1 /*********************************************************************************
2 * Copyright (c) 2013 David D. Marshall <ddmarsha@calpoly.edu>
3 *
4 * All rights reserved. This program and the accompanying materials
5 * are made available under the terms of the Eclipse Public License v1.0
6 * which accompanies this distribution, and is available at
7 * http://www.eclipse.org/legal/epl-v10.html
8 *
9 * Contributors:
10 * David D. Marshall - initial code and implementation
11 ********************************************************************************/
12 
13 #ifndef eli_mutil_dm_combination_hpp
14 #define eli_mutil_dm_combination_hpp
15 
16 #include <iterator>
17 #include <algorithm>
18 #include <functional>
19 
20 #include "eli/code_eli.hpp"
21 
22 namespace eli
23 {
24  namespace mutil
25  {
26  namespace dm
27  {
28  /* This code is intended to be similar to the std::next_permutation() function
29  * but instead returns the next next combination of std::distance(itb, itk) elements
30  * in the collection of elements [itb, ite). It is inspired by Matthieu N. answer at
31  * http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n
32  * The iterator used has to be bidirectional iterators.
33  */
34  template<typename it__, typename comp__>
35  bool next_combination(const it__ itb, it__ itk, const it__ ite, comp__ comp)
36  {
37  // catch case where either: (1) length of collection is zero, (2) desired combinations are zero,
38  // (3) desired combinations are the entire list, or (4) collection is only one element long
39  if ( (itb==ite) || (itb==itk) || (ite==itk) || (std::distance(itb, ite)==1) )
40  return false;
41 
42  // find the next combination
43  it__ it1=itk;
44  it__ it2=ite; --it2;
45  while (it1!=itb)
46  {
47  --it1;
48  if ( comp(*it1, *it2) )
49  {
50  it__ itj=itk;
51  while (!comp(*it1, *itj))
52  ++itj;
53 
54  std::iter_swap(it1, itj);
55  ++it1;
56  ++itj;
57  it2=itk;
58  std::rotate(it1, itj, ite);
59  while (itj != ite)
60  {
61  ++itj;
62  ++it2;
63  }
64  std::rotate(itk, it2, ite);
65  return true;
66  }
67  }
68  std::rotate(itb, itk, ite);
69  return false;
70  }
71 
72  template <typename it__>
73  bool next_combination(const it__ itb, it__ itk, const it__ ite)
74  {
75  return next_combination(itb, itk, ite, std::less<typename it__::value_type>());
76  }
77 
78  // TODO: There really should be a prev_combination() function as well
79  }
80  }
81 }
82 #endif
Definition: math.hpp:20
Derived1__::Scalar distance(const Eigen::MatrixBase< Derived1__ > &p1, const Eigen::MatrixBase< Derived2__ > &p2)
Definition: distance.hpp:33
bool next_combination(const it__ itb, it__ itk, const it__ ite, comp__ comp)
Definition: combination.hpp:35