Kata

Some students of Computer Science, received a challenge by their instructor.

"I'm going to show you the integer partions of some integers" - the instructor said. Next, he wrote in the blackboard some examples.

p(1) = 1 : 1 = 1
p(2) = 2 : 2 = 2, 2 = 1 + 1
p(3) = 3 : 3 = 3, 3 = 2 + 1, 3 = 1 + 1 + 1
p(4) = 5 : 4 = 4, 4 = 3 + 1, 4 = 2 + 2, 4 = 2 + 1 + 1, 4 = 1 + 1 + 1 + 1

"We need a code that may count the possible integer partions of an integer n, having k addens. For example, we've got the integer 4 and we want to know the amount of integer partitions for this number with 2 addens. The partitions [3,1] and [2,2] are the ones. So two possible partitions of length 2."

Basimilo, is a student of this class and prepared a code for the calculations. He created a code based on a generator for the partitions in Python, authored by David Epstein, available in the internet.

def parts(n):
    # Author: David Epstein
    if n == 0:
        yield []
        return
    for p in parts(n-1):
        yield [1] + p
        if p and (len(p) < 2 or p[1] > p[0]):
            yield [p[0] + 1] + p[1:]
            
def partitions(n,k):
    # my function, Basimilo :)
    c = 0
    for p in parts(n):
        if len(p) == k: c +=1
    return c

He also made a code in Javascript that makes the same thing:

function* parts(n) {
    //https://gist.github.com/k-hamada/8aa85ac9b334fb89ac4f
    // based on the work: https://pdfs.semanticscholar.org/9613/c1666b5e48a5035141c8927ade99a9de450e.pdf
    "use strict";
    if (n <= 0) throw new Error('positive integer only');
    yield [n];

    var x = new Array(n);
    x[0] = n;
    for (var i = 1; i < n; i++) x[i] = 1;

    var m = 0, h = 0, r, t;
    while (x[0] != 1) {
        if (x[h] == 2) {
            m += 1;
            x[h] = 1;
            h -= 1;
        } else {
            r = x[h] - 1;
            x[h] = r;

            t = m - h + 1;
            while (t >= r) {
                h += 1;
                x[h] = r;
                t -= r;
            }
            m = h + (t !== 0 ? 1 : 0);
            if (t > 1) {
                h += 1;
                x[h] = t;
            }
        }
        yield x.slice(0, m + 1);
    }
}

function partitions(n,k){
    // mine-Basimilo :-)
    var gen = parts(n);
    var c = 0;
    while (true) {
        var p = gen.next().value, l = p.length;
        if (l == k) c += 1;
        if (l == n) break;
    }
    return c;
}

The instructor tested Basimilo's codes, in python and javscript version and both gave good results for low numbers of n, k and said: "Well, this codes are useful for a first approach, only to know the result for low integers. You've got to keep in mind that you have bottlenecks in the generators that were thought to produce the partitions, not to count them."

Do you want to help? Prepare a code that may output the wanted result. See the example box for the Example Tests.

Features of the Random Tests:

1 <= k <= n <= 2000 (python)