Partition number (Enumerate $P(n, k)$)
(Mylib/Combinatorics/partition_number.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

• partition_number(int n, int k)
  • $P(0,0)$ ~ $P(n,k)$を列挙する。
  • Time complexity $O(nk)$

Requirements

Notes

Problems

References

• http://drken1215.hatenablog.com/entry/2018/01/16/222843
• https://mathtrain.jp/bunkatsu

Verified with

• test/aoj/DPL_5_J/main.test.cpp

Code

#pragma once
#include <vector>

namespace haar_lib {
  template <typename T>
  auto partition_number(int n, int k) -> std::vector<std::vector<T>> {
    std::vector<std::vector<T>> dp(n + 1, std::vector<T>(k + 1));
    dp[0][0] = 1;

    for (int i = 0; i <= n; ++i) {
      for (int j = 1; j <= k; ++j) {
        if (i - j >= 0)
          dp[i][j] = dp[i][j - 1] + dp[i - j][j];
        else
          dp[i][j] = dp[i][j - 1];
      }
    }

    return dp;
  }
}  // namespace haar_lib

#line 2 "Mylib/Combinatorics/partition_number.cpp"
#include <vector>

namespace haar_lib {
  template <typename T>
  auto partition_number(int n, int k) -> std::vector<std::vector<T>> {
    std::vector<std::vector<T>> dp(n + 1, std::vector<T>(k + 1));
    dp[0][0] = 1;

    for (int i = 0; i <= n; ++i) {
      for (int j = 1; j <= k; ++j) {
        if (i - j >= 0)
          dp[i][j] = dp[i][j - 1] + dp[i - j][j];
        else
          dp[i][j] = dp[i][j - 1];
      }
    }

    return dp;
  }
}  // namespace haar_lib

Back to top page