当前位置: 首页 > 知识库问答 >
问题:

按其编号生成整数分区

艾璞瑜
2023-03-14

我试图以字典顺序生成给定整数N 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

第三个是13。如何在不生成每个分区的情况下生成它(在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]
}

共有2个答案

漆雕嘉茂
2023-03-14
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)
. 
.
.
.
韩照
2023-03-14

下面是一些生成分区的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]
 类似资料:
  • 当试图从我的wsdl生成类时,我有以下错误: 无法执行目标组织。jvnet。jaxb2。maven2:maven-jaxb2-plugin:0.12.3:在hblws项目上生成(CreateWebServiceAccountV1)。测试:执行目标组织的CreateWebServiceAccountV1。jvnet。jaxb2。maven2:maven-jaxb2-plugin:0.12.3:生成失

  • 问题内容: 我有一些这样的数据: 我想查询它看起来像这样: …这样我就可以按数字连续的方式按GROUP BY分组。 另外,循环/游标也是不可能的,因为我正在处理大量数据,谢谢。 问题答案:

  • (重新发布,因为我之前的帖子没有得到任何回复) 我正在尝试编写一个Python代码,以将数字“n”的弱整数组合(分区)生成为“k”部分,但每个分区上都有最小值和最大值约束(见下面给出的示例)。此外,分区必须按字典顺序生成。我已经找到了一些相关的帖子,但没有能够实现。任何帮助都将不胜感激。 示例: 在k=3个部分中n=5的可能整数分区: [5,0,0],[4,1,0],[4,0,1],[3,2,0]

  • 我正在迁移jenkins工作流作业到新的基于模板的工作流作业。因为构建号被用作工作流生成的构建工件版本的一部分,所以我必须以大于旧工作流的数量开始新工作流的构建号。不幸的是,下一个构建号插件不适用于工作流管道。 有人知道这样做的好方法吗?

  • 问题内容: 如何根据当前日期返回包含过去四年的行集? 如果此查询在2010年12月31日运行,则应返回: 但是,如果它在2011年1月1日运行,则应返回: 这是我开始的工作,有两个查询返回了起始年份。我更喜欢第二种,因为转换为字符串对我来说有点脏。 但是我不知道如何生成行来充实它。在SQL Server中,我将像此页上的fn_nums函数一样使用CTE 。 问题答案: 这是一种方法: 或者: 或者

  • 我不是只想用第一个数字来完成这个操作,而是使用while循环和if条件,使我在键盘上输入的任何内容都变成一个整数。 你觉得问题出在哪里?请帮帮我.