Generating integer partition by its number

Question

I'm trying to generate decent partition of given integer number N numbered K in lexicographical order, e.g. for N = 5, K = 3 we got:

5 = 1 + 1 + 1 + 1 + 1
5 = 1 + 1 + 1 + 2
5 = 1 + 1 + 3
5 = 1 + 2 + 2
5 = 1 + 4
5 = 2 + 3
5 = 5

And the third one is 1 + 1 + 3. How can I generate this without generating every partition(in C language, but most of all I need algorithm)?

Going to find maximal number in partition(assuming we can find number of partitions d[i][j], where i is number and j is maximal integer in its partition), then decrease the original number and number we are looking for. So yes, I'm trying to use dynamic programming. Still working on code.

This doesn't work at all:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


FILE *F1, *F2;


main()
{
    long long i, j, p, n, k, l, m[102][102];
    short c[102];
    F1 = fopen("num2part.in", "r");
    F2 = fopen ("num2part.out", "w");
    n = 0;
    fscanf (F1, "%lld %lld", &n, &k);
    p = 0;
    m[0][0] = 1;
    for ( i = 0; i <= n; i++)
    {
        for (j = 1; j <= i; j++)
        {
            m[i][j] = m[i - j][j] + m[i][j - 1];
        }
        for (j = i + 1; j <= n; j++)
        {
            m[i][j] = m[i][i];
        }
    }
    l = n;
    p = n;
    j = n;
    while (k > 0)
    {
        while ( k < m[l][j])
        {
            if (j == 0)
            {
                while (l > 0)
                {
                    c[p] = 1;
                    p--;
                    l--;
                }
            break;
        }
        j--;
    }
    k -=m[l][j];
    c[p] = j + 1;
    p--;
    l -= c[p + 1];
    }
//printing answer here, answer is contained in array from c[p] to c[n]
}

Answer 1

Here is some example Python code that generates the partitions:

cache = {}
def p3(n,val=1):
    """Returns number of ascending partitions of n if all values are >= val"""
    if n==0:
        return 1 # No choice in partitioning
    key = n,val
    if key in cache:
        return cache[key]
    # Choose next value x
    r = sum(p3(n-x,x) for x in xrange(val,n+1))
    cache[key]=r
    return r

def ascending_partition(n,k):
    """Generate the k lexicographically ordered partition of n into integer parts"""
    P = []
    val = 1 # All values must be greater than this
    while n:
        # Choose the next number
        for x in xrange(val,n+1):
            count = p3(n-x,x)
            if k >= count:
                # Keep trying to find the correct digit
                k -= count
            elif count: # Check that there are some valid positions with this digit
                # This must be the correct digit for this location
                P.append(x)
                n -= x
                val = x
                break
    return P

n=5
for k in range(p3(n)):
    print k,ascending_partition(n,k)

It prints:

0 [1, 1, 1, 1, 1]
1 [1, 1, 1, 2]
2 [1, 1, 3]
3 [1, 2, 2]
4 [1, 4]
5 [2, 3]
6 [5]

This can be used to generate an arbitrary partition without generating all the intermediate ones. For example, there are 9253082936723602 partitions of 300.

print ascending_partition(300,10**15)

prints

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 5, 7, 8, 8, 11, 12, 13, 14, 14, 17, 17, 48, 52]