[c++] Creating all possible k combinations of n items in C++

To make it more complete, the following answer covers the case that the data set contains duplicate values. The function is written close to the style of std::next_permutation() so that it is easy to follow up.

template< class RandomIt >
bool next_combination(RandomIt first, RandomIt n_first, RandomIt last)
{
  if (first == last || n_first == first || n_first == last)
  {
    return false;
  }

  RandomIt it_left = n_first;
  --it_left;
  RandomIt it_right = n_first;

  bool reset = false;
  while (true)
  {
    auto it = std::upper_bound(it_right, last, *it_left);

    if (it != last)
    {
      std::iter_swap(it_left, it);
      if (reset)
      {
        ++it_left;
        it_right = it;
        ++it_right;
        std::size_t left_len = std::distance(it_left, n_first);
        std::size_t right_len = std::distance(it_right, last);
        if (left_len < right_len)
        {
          std::swap_ranges(it_left, n_first, it_right);
          std::rotate(it_right, it_right+left_len, last);
        }
        else
        {
          std::swap_ranges(it_right, last, it_left);
          std::rotate(it_left, it_left+right_len, n_first);
        }
      }
      return true;
    }
    else
    {
      reset = true;
      if (it_left == first)
      {
        break;
      }
      --it_left;
      it_right = n_first;
    }
  }
  return false;
}

The full data set is represented in the range [first, last). The current combination is represented in the range [first, n_first) and the range [n_first, last) holds the complement set of the current combination.

As a combination is irrelevant to its order, [first, n_first) and [n_first, last) are kept in ascending order to avoid duplication.

The algorithm works by increasing the last value A on the left side by swapping with the first value B on the right side that is greater than A. After the swapping, both sides are still ordered. If no such value B exists on the right side, then we start to consider increasing the second last on the left side until all values on the left side are not less than the right side.

An example of drawing 2 elements from a set by the following code:

  std::vector<int> seq = {1, 1, 2, 2, 3, 4, 5};
  do
  {
    for (int x : seq)
    {
      std::cout << x << " ";
    }
    std::cout << "\n";
  } while (next_combination(seq.begin(), seq.begin()+2, seq.end()));

gives:

1 1 2 2 3 4 5 
1 2 1 2 3 4 5 
1 3 1 2 2 4 5 
1 4 1 2 2 3 5 
1 5 1 2 2 3 4 
2 2 1 1 3 4 5 
2 3 1 1 2 4 5 
2 4 1 1 2 3 5 
2 5 1 1 2 3 4 
3 4 1 1 2 2 5 
3 5 1 1 2 2 4 
4 5 1 1 2 2 3 

It is trivial to retrieve the first two elements as the combination result if needed.

Examples related to c++

Method Call Chaining; returning a pointer vs a reference? How can I tell if an algorithm is efficient? Difference between opening a file in binary vs text How can compare-and-swap be used for a wait-free mutual exclusion for any shared data structure? Install Qt on Ubuntu #include errors detected in vscode Cannot open include file: 'stdio.h' - Visual Studio Community 2017 - C++ Error How to fix the error "Windows SDK version 8.1" was not found? Visual Studio 2017 errors on standard headers How do I check if a Key is pressed on C++

Examples related to algorithm

How can I tell if an algorithm is efficient? Find the smallest positive integer that does not occur in a given sequence Efficiently getting all divisors of a given number Peak signal detection in realtime timeseries data What is the optimal algorithm for the game 2048? How can I sort a std::map first by value, then by key? Finding square root without using sqrt function? Fastest way to flatten / un-flatten nested JSON objects Mergesort with Python Find common substring between two strings

Examples related to math

How to do perspective fixing? How to pad a string with leading zeros in Python 3 How can I use "e" (Euler's number) and power operation in python 2.7 numpy max vs amax vs maximum Efficiently getting all divisors of a given number Using atan2 to find angle between two vectors How to calculate percentage when old value is ZERO Finding square root without using sqrt function? Exponentiation in Python - should I prefer ** operator instead of math.pow and math.sqrt? How do I get the total number of unique pairs of a set in the database?

Examples related to combinations

Creating all possible k combinations of n items in C++ Generating combinations in c++ How to combine two strings together in PHP? How to calculate combination and permutation in R? Finding all possible combinations of numbers to reach a given sum Statistics: combinations in Python All combinations of a list of lists How to get all possible combinations of a list’s elements? Algorithm to return all combinations of k elements from n

Examples related to combinatorics

Creating all possible k combinations of n items in C++ Permutations between two lists of unequal length How can I print out all possible letter combinations a given phone number can represent? How to generate all permutations of a list?