Enumerate all integer partitions (tools/next_integer_partition.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-01-11 19:34:20+09:00
• Include: #include "tools/next_integer_partition.hpp"

(1)

template <tools::integral Z>
bool next_integer_partition(std::vector<Z>& a);

It generates the next integer partition of $n = \sum_{i = 0}^{|a| - 1} a_i$. It returns true if the next integer partition exists, false otherwise.

Example

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

Usage

std::vector<int> a{4};
do {
  // ...
} while (tools::next_integer_partition(a));

Constraints

• $|a| \geq 1$
• For any $i$ and $j$ such that $0 \leq i < j < |a|$, $a_i \geq a_j$.
• $a_{|a| - 1} \geq 1$

Time Complexity

• If you just call next_integer_partition, it takes only $O(n)$ time.
• If you enumerate all the integer partitions of $n$, it takes $O(n \cdot p(n))$ time where $p(n)$ is the number of integer partitions of $n$.

FYI, $p(n)$ for some representative $n$s are listed below.

$n$	$p(n)$
$10$	$42$
$20$	$627$
$30$	$5,604$
$40$	$37,338$
$50$	$204,226$
$60$	$966,467$
$70$	$4,087,968$
$80$	$15,796,476$
$90$	$56,634,173$
$100$	$190,569,292$

License

• CC0

Author

• anqooqie

(2)

template <tools::integral Z1, tools::integral Z2>
bool next_integer_partition(std::vector<std::pair<Z1, Z2>>& a);

It is almost equivalent to (1), but the integer partition $a$ is given as the run-length encoded list. In other words, the integer partition $(x_0, \cdots \text{($n_0$ times)} \cdots, x_0, x_1, \cdots \text{($n_1$ times)} \cdots, x_1, \ldots, x_{|a| - 1}, \cdots \text{($n_{|a| - 1}$ times)} \cdots, x_{|a| - 1})$ is given as $((x_0, n_0), (x_1, n_1), \ldots, (x_{|a| - 1}, n_{|a| - 1}))$.

Example

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

Usage

std::vector<std::pair<int, int>> a{ {4, 1} };
do {
  // ...
} while (tools::next_integer_partition(a));

Constraints

• $|a| \geq 1$
• For any $i$ and $j$ such that $0 \leq i < j < |a|$, $x_i > x_j$.
• $x_{|a| - 1} \geq 1$
• For any $i$ such that $0 \leq i < |a|$, $n_i \geq 1$.

Time Complexity

• If you just call next_integer_partition, it takes only $O(1)$ amortized time.
• If you enumerate all the integer partitions of $n$, it takes $O(p(n))$ time where $p(n)$ is the number of integer partitions of $n$.

License

• CC0

Author

• anqooqie

Depends on

• 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)

Verified with

• tests/next_integer_partition.test.cpp

Code

#ifndef TOOLS_NEXT_INTEGER_PARTITION
#define TOOLS_NEXT_INTEGER_PARTITION

#include <algorithm>
#include <cassert>
#include <ranges>
#include <tuple>
#include <utility>
#include <vector>
#include "tools/integral.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;
  }
}

#endif

#line 1 "tools/next_integer_partition.hpp"



#include <algorithm>
#include <cassert>
#include <ranges>
#include <tuple>
#include <utility>
#include <vector>
#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;
  }
}

Back to top page