tests/next_combination.test.cpp

View this file on GitHub
Last update: 2026-02-11 14:53:27+09:00

Depends on

Code

// competitive-verifier: STANDALONE

#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
#include "tools/assert_that.hpp"
#include "tools/next_combination.hpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  // enumerate all C(n, r) for small n
  for (int n = 0; n <= 8; ++n) {
    for (int r = 0; r <= n; ++r) {
      std::vector<int> v(n);
      for (int i = 0; i < n; ++i) v[i] = i;

      std::set<std::vector<int>> seen;
      std::vector<int> prev;
      int count = 0;
      do {
        std::vector<int> chosen(v.begin(), v.begin() + r);

        // chosen part is sorted
        assert_that(std::is_sorted(chosen.begin(), chosen.end()));

        // unchosen part is sorted
        assert_that(std::is_sorted(v.begin() + r, v.end()));

        // lexicographic order
        if (!prev.empty()) {
          assert_that(prev < chosen);
        }
        prev = chosen;

        // no duplicates
        assert_that(seen.insert(chosen).second);
        ++count;
      } while (tools::next_combination(v.begin(), v.begin() + r, v.end()));

      // correct number of combinations
      // C(n, r) = n! / (r! * (n - r)!)
      int expected = 1;
      for (int i = 0; i < r; ++i) {
        expected = expected * (n - i) / (i + 1);
      }
      assert_that(count == expected);
    }
  }

  return 0;
}

#line 1 "tests/next_combination.test.cpp"
// competitive-verifier: STANDALONE

#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
#line 1 "tools/assert_that.hpp"



#line 5 "tools/assert_that.hpp"
#include <cstdlib>

#define assert_that_impl(cond, file, line, func) do {\
  if (!cond) {\
    std::cerr << file << ':' << line << ": " << func << ": Assertion `" << #cond << "' failed." << '\n';\
    std::exit(EXIT_FAILURE);\
  }\
} while (false)
#define assert_that(...) assert_that_impl((__VA_ARGS__), __FILE__, __LINE__, __func__)


#line 1 "tools/next_combination.hpp"



#line 5 "tools/next_combination.hpp"
#include <iterator>

// 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 <std::random_access_iterator 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;
  }
}


#line 9 "tests/next_combination.test.cpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  // enumerate all C(n, r) for small n
  for (int n = 0; n <= 8; ++n) {
    for (int r = 0; r <= n; ++r) {
      std::vector<int> v(n);
      for (int i = 0; i < n; ++i) v[i] = i;

      std::set<std::vector<int>> seen;
      std::vector<int> prev;
      int count = 0;
      do {
        std::vector<int> chosen(v.begin(), v.begin() + r);

        // chosen part is sorted
        assert_that(std::is_sorted(chosen.begin(), chosen.end()));

        // unchosen part is sorted
        assert_that(std::is_sorted(v.begin() + r, v.end()));

        // lexicographic order
        if (!prev.empty()) {
          assert_that(prev < chosen);
        }
        prev = chosen;

        // no duplicates
        assert_that(seen.insert(chosen).second);
        ++count;
      } while (tools::next_combination(v.begin(), v.begin() + r, v.end()));

      // correct number of combinations
      // C(n, r) = n! / (r! * (n - r)!)
      int expected = 1;
      for (int i = 0; i < r; ++i) {
        expected = expected * (n - i) / (i + 1);
      }
      assert_that(count == expected);
    }
  }

  return 0;
}