Generating an integer section by its number

Question

I am trying to create a decent section of a given integer N with number K in lexicographical order, for example. 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 is 1 + 1 + 3 . How can I generate this without generating each section (in C, but most of all I need an algorithm)?

Switching to the search for the maximum number in the section (provided that we find the number of sections d[i][j] , where i is the number and j is the maximum integer in our section), then reduce the initial number and the number we are looking for . So yes, I'm trying to use dynamic programming. Still working on code.

This does not 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 an example of Python code that generates sections:

 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(nx,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(nx,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) 

He 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 create an arbitrary partition without generating all intermediate ones. For example, there are 9253082936723602 sections 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] 

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) . . . .