tests/next_permutation.test.cpp

View this file on GitHub
Last update: 2026-02-11 15:01:46+09:00

Depends on

Code

// competitive-verifier: STANDALONE

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

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

  // enumerate all P(n, r) for small n
  for (int n = 0; n <= 7; ++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);

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

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

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

  return 0;
}

#line 1 "tests/next_permutation.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_permutation.hpp"



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

namespace tools {
  template <std::random_access_iterator Iterator>
  bool next_permutation(const Iterator first, const Iterator k, const Iterator last) {
    std::reverse(k, last);
    return std::next_permutation(first, last);
  }
}


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

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

  // enumerate all P(n, r) for small n
  for (int n = 0; n <= 7; ++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);

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

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

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

  return 0;
}