Lazy combinations of c++ ranges view

Question

I am looking for an implementation of a ranges view that lazily creates the k combinations of a given range.

For example the range {1, 2, 3} with 2 combinations should return:

std::vector v {1,2,3};
auto rng = ranges::views::combinations<2>(v);
for(auto[a,b] : rng)
  std::cout << a << ' ' << b << '\n';
// 1, 2
// 1, 3
// 2, 3

So similar to Pythons itertools.combinations() module.

I found the implementations from this question. But they are not for ranges and not lazy.

Solution

My current solution thanks to the answer of this question:

#include <iostream>
#include <range/v3/all.hpp>
#include <vector>

// credits to
// https://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n/1617797#1617797
template <typename Iterator>
bool next_combination(const Iterator first, Iterator k, const Iterator last) {
  /* Credits: Mark Nelson http://marknelson.us */
  if ((first == last) || (first == k) || (last == k)) return false;
  Iterator i1 = first;
  Iterator i2 = last;
  ++i1;
  if (last == i1) return false;
  i1 = last;
  --i1;
  i1 = k;
  --i2;
  while (first != i1) {
    if (*--i1 < *i2) {
      Iterator j = k;
      while (!(*i1 < *j)) ++j;
      std::iter_swap(i1, j);
      ++i1;
      ++j;
      i2 = k;
      std::rotate(i1, j, last);
      while (last != j) {
        ++j;
        ++i2;
      }
      std::rotate(k, i2, last);
      return true;
    }
  }
  std::rotate(first, k, last);
  return false;
}

int main() {
  std::vector<int> values{1, 2, 3, 4};
  auto const comb_size = 3;
  auto lazycombo = [values, comb_size]() mutable {
    bool ok = next_combination(values.begin(), values.begin() + comb_size,
                               values.end());
    return std::span(values.begin(), values.begin() + comb_size);
  };
  auto combinations = ranges::views::generate_n(lazycombo, 3);
  for (auto combination : combinations)
    std::cout << combination[0] << ' ' << combination[1] << ' '
              << combination[2] << '\n';
}

link

Does it have to be C++20's ranges? If yes, maybe add a C++20 tag to your question. Else there is also good old [`std::next_permutation`](https://en.cppreference.com/w/cpp/algorithm/next_permutation). — nada, Dec 01 '20 at 11:37

score 2 · Accepted Answer · answered Dec 01 '20 at 14:22

Make "everything" lazy

Totally untested code

auto lazycombo = [values, comb_size]() mutable { 
  bool ok = next_combination(values.begin(), values.begin() + comb_size, values.end());
  return std::span(values.begin(), values.begin()+comb_size);
}

see next_combination.

Now using your

auto combinationIdx = ranges::views::generate(lazycombo);

Which should be generate_n as there is no way to stop generate, where the n should be the number of possible combinations. .

Crazy method. But it works! Thanks! I updated my question with a working solution based on your answer. Thank you! — The Shmoo, Dec 01 '20 at 15:27

Lazy combinations of c++ ranges view

Solution

1 Answers1