标签: integer-partition

查找总和数的多少组合(代码中的变量n).例如:

3 = 1 + 1 + 1 = 2 + 1 = 3 => ANS为3

5 = 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1 => ANS是7

在下面的例子中,m是最大数,n是sum,目的是找出它有多少(和)组合.

我只是想知道为什么p(n, m) = p(n, m - 1) + p(n - m, m)？ …

我正在尝试为Python找到或开发Integer Partitioning代码.

FYI,整数分区将给定的整数n表示为小于n的整数之和.例如,整数5可以表示为4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1

我找到了很多解决方案.http://homepages.ed.ac.uk/jkellehe/partitions.php和http://code.activestate.com/recipes/218332-generator-for-integer-partitions/

但是,我真正想要的是限制分区数量.

比如说,#分区k = 2,一个程序只需要显示5 = 4 + 1 = 3 + 2,

如果k = 3,5 = 3 + 1 + 1 = 2 + 2 + 1

我正在构建一个包含Partitions类的C++库.我正在尝试实现共轭(下面解释),我无法让它工作.

我的班级成员是:

size_t _size;
size_t _length;
std::vector<int> _parts;

例如,整数分区[5,4,4,1]具有

_size = 14   // 5 + 4 + 4 + 1
_length = 4  // 4 nonzero parts
_parts[0] = 5
_parts[1] = 4
_parts[2] = 4
_parts[3] = 1 
_parts[i] = junk // i>3

如果分区是[m_1,m_2,...,m_k],那么共轭就[n_1,n_2,...,n_l]在哪里

l = m_1 // length and the first part are switched
n_i = sum{ m_j | m_j > i}

例如,共轭[5,4,4,1]是[4,3,3,3,1].另一种看待这种情况的方法是将分区绘制为单位正方形的行,其中第一行中的正方形i是m_i.读取列的高度然后给出共轭.对于同一个例子,图片是

1| …

对于排列,给定N和k,我有一个函数,找到按字典顺序k排列的N排列.另外,给定一个排列perm,我有一个函数,可以在所有排列中找到排列的词典索引N.为此,我使用了本答案中建议的"因子分解" .

现在我想对整数分区做同样的事情N.例如,因为N=7,我希望能够在索引(左)和分区(右)之间来回:

 0 ( 7 )
 1 ( 6 1 )
 2 ( 5 2 )
 3 ( 5 1 1 )
 4 ( 4 3 )
 5 ( 4 2 1 )
 6 ( 4 1 1 1 )
 7 ( 3 3 1 )
 8 ( 3 2 2 )
 9 ( 3 2 1 1 )
10 ( …

我正在尝试生成以字典顺序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> …

鉴于两个整数n和d,我想构建长度的所有非负元组的列表d是总结到n,包括所有排列.这类似于整数分区问题,但解决方案要简单得多.例如 d==3:

[
    [n-i-j, j, i]
    for i in range(n+1)
    for j in range(n-i+1)
]

这可以很容易地扩展到更多尺寸,例如d==5:

[
    [n-i-j-k-l, l, k, j, i]
    for i in range(n+1)
    for j in range(n-i+1)
    for k in range(n-i-j+1)
    for l in range(n-i-j-l+1)
]

我现在想制作d,即嵌套循环的数量,一个变量,但我不知道如何嵌套循环.

任何提示？

对于正整数n和k，令“ n的k分区”为加起来为n 的k个不同正整数的排序列表，并令给定的n的k分区的“排名”为其在列表中的位置。所有这些列表按字典顺序排序的列表，从 0 开始。