Combination

next_combination.h

#pragma once

#include <algorithm>

template<class Iterator>
bool next_combination(Iterator first1, Iterator last1, Iterator first2, Iterator last2) {
  if((first1 == last1) || (first2 == last2)) return false;
  Iterator m1 = last1, m2 = last2; --m2;
  while(--m1 != first1 && !(*m1 < *m2)) {}
  const bool result = !((m1 == first1) && !(*first1 < *m2));
  if(result) {
    while(first2 != m2 && !(*m1 < *first2)) ++first2;
    first1 = m1;
    std::iter_swap(first1++, first2++);
  }
  if((first1 != last1) && (first2 != last2)) {
    m1 = last1, m2 = first2;
    while((m1 != first1) && (m2 != last2)) std::iter_swap(--m1, m2), ++m2;
    std::reverse(first1, m1);
    std::reverse(first1, last1);
    std::reverse(m2, last2);
    std::reverse(first2, last2);
  }
  return result;
}

template<class Iterator>
bool next_combination(Iterator first, Iterator middle, Iterator last) {
  return next_combination(first, middle, middle, last);
}