55 lines
1.4 KiB
C++
55 lines
1.4 KiB
C++
// Reference: https://en.wikipedia.org/wiki/Lah_number#Identities_and_relations
|
|
|
|
#include <algorithm>
|
|
#include <iomanip>
|
|
#include <iostream>
|
|
#include <map>
|
|
#include <gmpxx.h>
|
|
|
|
using integer = mpz_class;
|
|
|
|
class unsigned_lah_numbers {
|
|
public:
|
|
integer get(int n, int k);
|
|
private:
|
|
std::map<std::pair<int, int>, integer> cache_;
|
|
};
|
|
|
|
integer unsigned_lah_numbers::get(int n, int k) {
|
|
if (k == n)
|
|
return 1;
|
|
if (k == 0 || k > n)
|
|
return 0;
|
|
auto p = std::make_pair(n, k);
|
|
auto i = cache_.find(p);
|
|
if (i != cache_.end())
|
|
return i->second;
|
|
integer result = (n - 1 + k) * get(n - 1, k) + get(n - 1, k - 1);
|
|
cache_.emplace(p, result);
|
|
return result;
|
|
}
|
|
|
|
void print_lah_numbers(unsigned_lah_numbers& uln, int n) {
|
|
std::cout << "Unsigned Lah numbers up to L(12,12):\nn/k";
|
|
for (int j = 1; j <= n; ++j)
|
|
std::cout << std::setw(11) << j;
|
|
std::cout << '\n';
|
|
for (int i = 1; i <= n; ++i) {
|
|
std::cout << std::setw(2) << i << ' ';
|
|
for (int j = 1; j <= i; ++j)
|
|
std::cout << std::setw(11) << uln.get(i, j);
|
|
std::cout << '\n';
|
|
}
|
|
}
|
|
|
|
int main() {
|
|
unsigned_lah_numbers uln;
|
|
print_lah_numbers(uln, 12);
|
|
std::cout << "Maximum value of L(n,k) where n == 100:\n";
|
|
integer max = 0;
|
|
for (int k = 0; k <= 100; ++k)
|
|
max = std::max(max, uln.get(100, k));
|
|
std::cout << max << '\n';
|
|
return 0;
|
|
}
|