tests/next_integer_partition.test.cpp

• View this file on GitHub
• Last update: 2026-01-11 19:34:20+09:00

Depends on

• Assertion macro (tools/assert_that.hpp)
• Concept for integral types including tools::int128_t and tools::uint128_t (tools/integral.hpp)
• std::is_integral extended for tools::int128_t and tools::uint128_t (tools/is_integral.hpp)
• Enumerate all integer partitions (tools/next_integer_partition.hpp)

Code

// competitive-verifier: STANDALONE

#include <iostream>
#include <utility>
#include <vector>
#include "tools/assert_that.hpp"
#include "tools/next_integer_partition.hpp"

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

  {
    std::vector<int> a{1};
    assert_that(!tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{1});
  }
  {
    std::vector<int> a{2};
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{1, 1});
    assert_that(!tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{2});
  }
  {
    std::vector<int> a{3};
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{2, 1});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{1, 1, 1});
    assert_that(!tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{3});
  }
  {
    std::vector<int> a{4};
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{3, 1});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{2, 2});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{2, 1, 1});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{1, 1, 1, 1});
    assert_that(!tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{4});
  }
  {
    std::vector<int> a{5};
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{4, 1});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{3, 2});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{3, 1, 1});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{2, 2, 1});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{2, 1, 1, 1});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{1, 1, 1, 1, 1});
    assert_that(!tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{5});
  }

  {
    std::vector<int> a{60};
    int p = 0;
    do {
      ++p;
    } while (tools::next_integer_partition(a));
    assert_that(p == 966467);
  }

  {
    std::vector<std::pair<int, int>> a{{1, 1}};
    assert_that(!tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{1, 1}});
  }
  {
    std::vector<std::pair<int, int>> a{{2, 1}};
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{1, 2}});
    assert_that(!tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{2, 1}});
  }
  {
    std::vector<std::pair<int, int>> a{{3, 1}};
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{2, 1}, {1, 1}});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{1, 3}});
    assert_that(!tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{3, 1}});
  }
  {
    std::vector<std::pair<int, int>> a{{4, 1}};
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{3, 1}, {1, 1}});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{2, 2}});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{2, 1}, {1, 2}});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{1, 4}});
    assert_that(!tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{4, 1}});
  }
  {
    std::vector<std::pair<int, int>> a{{5, 1}};
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{4, 1}, {1, 1}});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{3, 1}, {2, 1}});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{3, 1}, {1, 2}});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{2, 2}, {1, 1}});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{2, 1}, {1, 3}});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{1, 5}});
    assert_that(!tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{5, 1}});
  }

  {
    std::vector<std::pair<int, int>> a{{60, 1}};
    int p = 0;
    do {
      ++p;
    } while (tools::next_integer_partition(a));
    assert_that(p == 966467);
  }

  return 0;
}

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

#include <iostream>
#include <utility>
#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_integer_partition.hpp"



#include <algorithm>
#include <cassert>
#include <ranges>
#include <tuple>
#line 1 "tools/integral.hpp"



#line 1 "tools/is_integral.hpp"



#include <type_traits>

namespace tools {
  template <typename T>
  struct is_integral : std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = tools::is_integral<T>::value;
}


#line 5 "tools/integral.hpp"

namespace tools {
  template <typename T>
  concept integral = tools::is_integral_v<T>;
}


#line 11 "tools/next_integer_partition.hpp"

namespace tools {
  template <tools::integral Z>
  bool next_integer_partition(std::vector<Z>& a) {
    assert(!a.empty());
    assert(a.back() >= 1);
    assert(std::ranges::all_of(a | std::views::adjacent<2>, [](const auto& pair) { return std::get<0>(pair) >= std::get<1>(pair); }));

    if (a.front() == 1) {
      const Z sum = a.size();
      a.clear();
      a.push_back(sum);
      return false;
    }

    Z remain = 0;
    while (a.back() == 1) {
      ++remain;
      a.pop_back();
    }

    --a.back();
    ++remain;
    const Z bound = a.back();
    while (remain > 0) {
      a.push_back(std::min(remain, bound));
      remain -= a.back();
    }

    return true;
  }

  template <tools::integral Z1, tools::integral Z2>
  bool next_integer_partition(std::vector<std::pair<Z1, Z2>>& a) {
    assert(!a.empty());
    assert(a.back().first >= 1);
    assert(std::ranges::all_of(a | std::views::adjacent<2>, [](const auto& pair) { return std::get<0>(pair).first > std::get<1>(pair).first; }));
    assert(std::ranges::all_of(a, [](const auto& a_i) { return a_i.second >= 1; }));

    if (a.front().first == 1) {
      assert(a.size() == 1);
      a.front() = std::pair<Z1, Z2>{a.front().second, 1};
      return false;
    }

    Z1 remain = 0;
    if (a.back().first == 1) {
      remain = a.back().second;
      a.pop_back();
    }

    assert(!a.empty());
    assert(a.back().first >= 2);
    --a.back().second;
    remain += a.back().first;
    const Z1 bound = a.back().first - 1;
    if (a.back().second == 0) {
      a.pop_back();
    }

    a.emplace_back(bound, remain / bound);
    remain -= bound * a.back().second;
    if (remain > 0) {
      a.emplace_back(remain, 1);
    }

    return true;
  }
}


#line 8 "tests/next_integer_partition.test.cpp"

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

  {
    std::vector<int> a{1};
    assert_that(!tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{1});
  }
  {
    std::vector<int> a{2};
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{1, 1});
    assert_that(!tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{2});
  }
  {
    std::vector<int> a{3};
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{2, 1});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{1, 1, 1});
    assert_that(!tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{3});
  }
  {
    std::vector<int> a{4};
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{3, 1});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{2, 2});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{2, 1, 1});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{1, 1, 1, 1});
    assert_that(!tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{4});
  }
  {
    std::vector<int> a{5};
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{4, 1});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{3, 2});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{3, 1, 1});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{2, 2, 1});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{2, 1, 1, 1});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{1, 1, 1, 1, 1});
    assert_that(!tools::next_integer_partition(a));
    assert_that(a == std::vector<int>{5});
  }

  {
    std::vector<int> a{60};
    int p = 0;
    do {
      ++p;
    } while (tools::next_integer_partition(a));
    assert_that(p == 966467);
  }

  {
    std::vector<std::pair<int, int>> a{{1, 1}};
    assert_that(!tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{1, 1}});
  }
  {
    std::vector<std::pair<int, int>> a{{2, 1}};
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{1, 2}});
    assert_that(!tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{2, 1}});
  }
  {
    std::vector<std::pair<int, int>> a{{3, 1}};
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{2, 1}, {1, 1}});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{1, 3}});
    assert_that(!tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{3, 1}});
  }
  {
    std::vector<std::pair<int, int>> a{{4, 1}};
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{3, 1}, {1, 1}});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{2, 2}});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{2, 1}, {1, 2}});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{1, 4}});
    assert_that(!tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{4, 1}});
  }
  {
    std::vector<std::pair<int, int>> a{{5, 1}};
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{4, 1}, {1, 1}});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{3, 1}, {2, 1}});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{3, 1}, {1, 2}});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{2, 2}, {1, 1}});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{2, 1}, {1, 3}});
    assert_that(tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{1, 5}});
    assert_that(!tools::next_integer_partition(a));
    assert_that(a == std::vector<std::pair<int, int>>{{5, 1}});
  }

  {
    std::vector<std::pair<int, int>> a{{60, 1}};
    int p = 0;
    do {
      ++p;
    } while (tools::next_integer_partition(a));
    assert_that(p == 966467);
  }

  return 0;
}

Back to top page