按其編號生成整數分區

Question

我試圖按照字典順序（例如，編號）生成編號爲K的給定整數N的像樣分區。對於N = 5, K = 3我們得到：

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 

，第三個是1 + 1 + 3。 如何在不生成每個分區（使用C語言，但最重要的是我需要算法）的情況下生成此分區？

會發現在分區最大數量（假設我們可以發現分區d[i][j]，數其中i是數量和j是它的分區的最大整數），則減少原來的號碼和電話號碼，我們所期待的。所以是的，我試圖使用動態編程。仍在研究代碼。

這並不在所有的工作：

#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

下面是一些產生分區例如Python代碼：

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) 

它打印：

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] 

這可能是用於生成任意分區而不生成所有中間分區。例如，有9253082936723602個分區300

print ascending_partition(300,10**15) 

打印

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