79367067

Date: 2025-01-18 11:48:08
Score: 0.5
Natty:
Report link

For everyone coming here in search of an implementation:

I used the code snippet from the original question and wrote a command line tool for it. When compiled it takes n and m as command line arguments (with input parsing yoinked from https://stackoverflow.com/a/2797823/25165526)

I also included caching to drastically speed up run time. (for inputs n = 134, m = 32 it went from 44 seconds to 0.008 seconds)

#include <iostream>
#include <string>
#include <utility>
#include <unordered_map>
#include <boost/container_hash/hash.hpp>

long long p (long long n, long long m) {
    using pair = std::pair<int, int>;
    static std::unordered_map<pair, long long, boost::hash<pair>> cache = {};
    
    pair key = pair(n, m);
    if (cache.contains(key)) {
        return cache[key];
    }

    long long intermediate;
    if (n == m) {
        intermediate = 1 + p(n, m - 1);
        cache[key] = intermediate;
        return intermediate;
    }
    if (m == 0 || n < 0) {
        cache[key] = 0;
        return 0;
    }
    if (n == 0 || m == 1) {
        cache[key] = 1;
        return 1;
    }

    intermediate = p(n, m - 1) + p(n - m, m);
    cache[key] = intermediate;
    return intermediate;
}

int parse_arg(std::string arg) {
    try {
        std::size_t pos;
        int x = std::stoi(arg, &pos);
        if (pos < arg.size()) {
            std::cerr << "Trailing characters after number: " << arg << '\n';
        }
        return x;
    } catch (std::invalid_argument const &ex) {
        std::cerr << "Invalid number: " << arg << '\n';
    } catch (std::out_of_range const &ex) {
        std::cerr << "Number out of range: " << arg << '\n';
    }
    return -1;
}

int main(int argc, char *argv[]) {
    if (argc != 3) {
        std::cout << "Use with arguments <n> <k> where n is the target value and k is the maximum value a sum element may have" << std::endl;
        return -1;
    }

    // parse inputs
    int n, k;
    n = parse_arg((std::string) argv[1]);
    k = parse_arg((std::string) argv[2]);
    
    // calculate all possible sums
    long long possible_sums = p(n, k);

    std::cout << possible_sums << std::endl;
    return 0;
}

comopiled with:

g++ -std=c++20 -o integer_partition integer_partition.cpp
Reasons:
  • Blacklisted phrase (1): stackoverflow
  • Long answer (-1):
  • Has code block (-0.5):
  • Low reputation (1):
Posted by: user25165526