Next combination as n-choose-r (tools/next_combination.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2021-07-17 23:00:45+09:00
• Include: #include "tools/next_combination.hpp"
• Link: https://stackoverflow.com/questions/5095407/all-combinations-of-k-elements-out-of-n/5097100#5097100

template <typename Iterator>
bool next_combination(Iterator first, Iterator k, Iterator last);

It generates the next combination as n-choose-r. It returns true if the next combination exists, false otherwise.

Usage

// 9-choose-3
int k = 3;
do {
  std::cout << std::string(s.begin(), std::next(s.begin(), k)) << std::endl;
} while (tools::next_combination(s.begin(), std::next(s.begin(), k), s.end()));

Constraints

• first $\leq$ k $\leq$ last

Time Complexity

• Not analyzed yet

References

• Stack Overflow

License

• CC BY-SA 3.0

Author

• Thomas Draper

Code

#ifndef TOOLS_NEXT_COMBINATION_HPP
#define TOOLS_NEXT_COMBINATION_HPP

#include <algorithm>

// Source: https://stackoverflow.com/questions/5095407/all-combinations-of-k-elements-out-of-n/5097100#5097100
// License: CC BY-SA 3.0
// Author: Thomas Draper

namespace tools {

  template <typename Iterator>
  bool next_combination(const Iterator first, Iterator k, const Iterator last) {
    if ((first == last) || (first == k) || (last == k)) return false;
    Iterator itr1 = first;
    Iterator itr2 = last;
    ++itr1;
    if (last == itr1) return false;
    itr1 = last;
    --itr1;
    itr1 = k;
    --itr2;
    while (first != itr1) {
      if (*--itr1 < *itr2) {
        Iterator j = k;
        while (!(*itr1 < *j)) ++j;
        ::std::iter_swap(itr1, j);
        ++itr1;
        ++j;
        itr2 = k;
        ::std::rotate(itr1, j, last);
        while (last != j) {
          ++j;
          ++itr2;
        }
        ::std::rotate(k, itr2, last);
        return true;
      }
    }
    ::std::rotate(first, k, last);
    return false;
  }
}

#endif

#line 1 "tools/next_combination.hpp"



#include <algorithm>

// Source: https://stackoverflow.com/questions/5095407/all-combinations-of-k-elements-out-of-n/5097100#5097100
// License: CC BY-SA 3.0
// Author: Thomas Draper

namespace tools {

  template <typename Iterator>
  bool next_combination(const Iterator first, Iterator k, const Iterator last) {
    if ((first == last) || (first == k) || (last == k)) return false;
    Iterator itr1 = first;
    Iterator itr2 = last;
    ++itr1;
    if (last == itr1) return false;
    itr1 = last;
    --itr1;
    itr1 = k;
    --itr2;
    while (first != itr1) {
      if (*--itr1 < *itr2) {
        Iterator j = k;
        while (!(*itr1 < *j)) ++j;
        ::std::iter_swap(itr1, j);
        ++itr1;
        ++j;
        itr2 = k;
        ::std::rotate(itr1, j, last);
        while (last != j) {
          ++j;
          ++itr2;
        }
        ::std::rotate(k, itr2, last);
        return true;
      }
    }
    ::std::rotate(first, k, last);
    return false;
  }
}

Back to top page