按整数分区的数目生成整数分区

Question

我试图生成给定整数N的体面分区，按字典顺序编号为K，例如，对于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)
. 
.
.
.