Integer Partition (algorithm and recursion)

Question

Finding how many combinations of a sum number (the variable n in code). For ex.:

3 = 1+1+1 = 2+1 = 3 => ANS is 3

5 = 5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1 => ANS is 7

In the following example, m is the max number and n is sum, the aim is to find how many (sum) combination does it have.

I just want to know why do p(n, m) = p(n, m - 1) + p(n - m, m) ?

The code here:

int p (int n, int m)
{
    if (n == m)
        return 1 + p(n, m - 1);
    if (m == 0 || n < 0)
        return 0;
    if (n == 0 || m == 1)
        return 1;

    return p(n, m - 1) + p(n - m, m);

}

Appreciated!

I think it's combination, there's no different in 3+2 and 2+3 in this case. — PlusA
– PlusA, Commented Dec 27, 2012 at 11:27
It's not same, the function here using the number not greater than m (less than or equal to), but the case in wiki is using the number greater than or equal to k. — PlusA
– PlusA, Commented Dec 27, 2012 at 11:32
I presume you'd like us to justify the recurrence relation for p(n,m) by combinatorial argument, but you forgot to give a combinatorial definition for that function! That's not a fair ask. — Colonel Panic
– Colonel Panic, Commented Aug 19, 2013 at 11:12

mhsekhavat · Accepted Answer · 2013-08-22 08:51:32Z

Consider all ways of resulting n by adding some numbers less than or equal to m. As you said, we call this p(n,m). For example, p(7,3)=8 because there are 8 ways to make 7 out of numbers less than 3 as listed below: (For simplicity we can assume that always we add numbers in order from greatest to least)

3+3+1
3+2+2
3+2+1+1
3+1+1+1+1
2+2+2+1
2+2+1+1+1
2+1+1+1+1+1
1+1+1+1+1+1+1

Now we can split these combinations in two groups:

Combinations whose first element is equal to m(=3 in our example:)
- 3+3+1
- 3+2+2
- 3+2+1+1
- 3+1+1+1+1
Combinations whose first element is less than m:
- 2+2+2+1
- 2+2+1+1+1
- 2+1+1+1+1+1
- 1+1+1+1+1+1+1

Because every member of combinations of p(n,m) will be either in Group1 or in Group2, we can say p(n,m)=size(Group1) + size(Group2). Now if we prove that size(Group1)=p(n-m, m) and size(Group2)=p(n,m-1) by substitution we reach p(n,m)=p(n-m,m)+p(n,m-1)

Prove for `size(Group1)=p(n-m, m)`:

By aforementioned definition p(n-m, m) is number of ways of resulting n-m by adding some numbers less than or equal to m.

If you append m to each combination of p(n-m, m), it will result a member of Group1. so p(n-m, m) <= size(Group1)
If you remove first m of each member of Group1, it will result a combination for p(n-m, m). so size(Group1) <= p(n-m, m)

=> size(Group1) = p(n-m, m). In our example:

Group1 <===correspondence===> p(4, 3) :

7=3+3+1 <===========> 3+1=4
7=3+2+2 <===========> 2+2=4
7=3+2+1+1 <=======> 2+1+1=4
7=3+1+1+1+1 <===> 1+1+1+1=4

So there is one to one correspondence between any member of p(n-m,m) and Group1 and their size is equal.

Prove for `size(Group2)=p(n, m-1)`:

By definition, p(n,m-1) is the number of ways to result n by adding some numbers less than or equal to m-1 (less than m). If you re-read the definition of Group2, you will see that these two definitions are same as each other. => size(Group2) = p(n, m-1)

can anyone tell me how the values 3+3+1 3+2+2 3+2+1+1 3+1+1+1+1 are generated after p(4,3) considering the return values 0&1.

Community · Accepted Answer · 2021-05-05 05:42:14Z

        / 0 (k>n)
p(k,n)={  1 (k=n)
        \ p(k+1,n)+p(k,n-k) (k<n)

Number of partitions of n is p(1,n).

p(k,n) is number of partitions of n, allowing only addends >=k.

Like the OP's recursive formula, it adds them (as luiges90 put it) one by one (with the added inefficiency of numerous zeroes). Fortunately, though, it can be calculated inside an array with great speed:

#include <stdio.h>

/* 406 is the largest n for which p(n) fits in 64 bits */
#define MAX 406
long long int pArray[MAX][MAX];

/* Emulate array starting at 1: */
#define p(k,n) pArray[k-1][n-1]

int main(int argc, char **argv) {
    int n, k;
    for (n = 1; n < MAX; n++) {
        for (k = n; k > 0; k--) {
            if (k > n) {
                p(k, n) = 0;
            } else if (k == n) {
                p(k, n) = 1;
            } else {
                p(k, n) = p(k, n - k) + p(k + 1, n);
            }
        }
    }
    for (n = 1; n < MAX; n++) {
        printf("p(%d)=%lld\n", n, p(1, n));
    }
}

btilly · Accepted Answer · 2013-08-20 15:41:16Z

First for more than you could want to know about this function, see http://mathworld.wolfram.com/PartitionFunctionP.html.

As for this formula, remember that p(n, m) is defined to be the number of partitions of n whose largest member is at most m.

Therefore p(n, m) is the number of partitions of m whose largest member is at most m. Let us divide them according to whether the largest member actually is m.

The number of partitions whose largest member is m is the number of ways of filling in n = m + ... which is the number of partitions of n-m whose largest member is at most m which by definition is p(n-m, m).

The number of partitions of n whose largest member is at most m-1 is by definition p(n, m-1).

Therefore p(n, m) = p(n-m, m) + p(n, m-1).

Hui Zheng · Accepted Answer · 2012-12-27 13:35:22Z

2

Denote p(n, m) as the number of all combinations whose sum is n and each addend is less than or equals to m. The key point here is to prove the following recursive equation:

p(n, m) - p(n, m - 1) = p(n-m, m)          (1)

The left side of (1) is the difference of p(n, m) and p(n, m - 1), which are the number of all combinations that contains at least one m as addend, and leftover's sum is n-m(such that the overall is n), besides each addend is less than or equal to m. But that exactly means p(n-m, m), which is the right side of (1).

Obviously, the answer of the question should be p(n, n).

answered Dec 27, 2012 at 13:35

Hui Zheng

10.2k2 gold badges37 silver badges40 bronze badges

2 Comments

PlusA Over a year ago

I'm just not understand why the leftover is p(n-m, m), can explain in other way? It's better if you can explain in Chinese and more detail!

Hui Zheng Over a year ago

@PlusA I'm not sure whether it's good or not to answer in Chinese. Let's think in this way: what's the character of all combinations that are in P(n, m) but not in p(n, m-1)? First, these combinations must have a fixed member, namely, m(otherwise it will also belong to p(n, m-1)). Secondly, the remaining members's sum must be n-m(s.t. the overall sum is n). Besides, the remaining members can be at most m. Hence the number of these combinations should be p(n-m, m). Is that clear?

user25165526 · Accepted Answer · 2025-01-18 12:06:55Z

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(int n, int 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

Collectives™ on Stack Overflow

Integer Partition (algorithm and recursion)

5 Answers 5

Prove for `size(Group1)=p(n-m, m)`:

Prove for `size(Group2)=p(n, m-1)`:

1 Comment

Comments

Comments

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Prove for size(Group1)=p(n-m, m):

Prove for size(Group2)=p(n, m-1):

1 Comment

Comments

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related

Prove for `size(Group1)=p(n-m, m)`:

Prove for `size(Group2)=p(n, m-1)`: