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]
}

• zch: Use dynamic programming to find number of (n,k)-partitions for n<N, k<K. With it, it's easy.
• siziyman: Trying 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, still working on it.

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]

• siziyman: Thanks, I have the code that generates all partitions, but there should be solution for generating one partition with decent number in this order(generating all works too slow).
• Peter de Rivaz: The code here generates a single partition at a time. You can simply call ascending_partition(n,k) with whatever values of n and k you desire. I just put in the loop for testing.
• Bernhard Barker: This still has the overhead of having to work through all the partitions, right? (as opposed to simply calculating the required one)
• Peter de Rivaz: @Dukeling No, I think the complexity is roughly O(n^3) and does not depend on k. The example shows it computing the partition for a huge value of k almost instantly.

Answer 2

def _yieldParts(num,lt):
 ''' It generate a comination set'''
 if not num:
 yield ()
 for i in range(min(num,lt),0,-1):
 for parts in _yieldParts(num-i,i):
 yield (i,)+parts
def patition(number,kSum,maxIntInTupple):
 ''' It generates a comination set with sum of kSum is equal to number
 maxIntInTupple is for maximum integer can be in tupple'''
 for p in _yieldParts(number,maxIntInTupple):
 if(len(p) <=kSum):
 if(len(p)<kSum):
 while len(p) < kSum:
 p+=(0,)
 print p
patition(40,8,40)
Output:
-------
(40,0,0,0,0,0,0,0)
(39,1,0,0,0,0,0,0)
. 
.
.
.

• Sulthan Allaudeen: Give explanation to your code. Code only answers are not appreciated.
• user3472760: I have given comments for function. You can get some idea.