问题标签 [integer-partition]

我希望在 k 部分中枚举 n 的所有分区。

所以对于 p(5,3) 我会得到 2 个 k = 3 => (3,1,1), (2,2,1) 的分区。

这是我通过搜索和查看 stackoverflow 发现的：

^^^^ 这是我想要的形式，

事实上，找到 k 个部分的总和很容易，您返回 p(n-1, k-1) + p(nk,k)。至于我，我需要像这样列出每个元素 [(3,1,1), (2,2,1)]。

我的主要问题是递归地“构建”这些分区。你会如何解决这个问题？

编辑

如果你得到基本情况 k = 1，则加 + 1，k-1 次。(4,1) 然后 (4,1,1)

如果您得到基本情况 k = n，请拆分并删除每个部分。

像这样：（3,3）然后（3,3,3）然后（2,2,2）

如果你得到基本情况 k < n，什么都没有

基本上，我的问题是将基本情况“堆叠”到顶部并获得完整列表 p(6,3) = [(2,2,2), (4,1,1), (3,2 ,1)]

这是一个家庭作业问题，必须使用动态编程方法来解决。

到目前为止，我设法做的是：

让 f(x) 表示 x 可以写的次数：

那么 f(x) = f(x - 1) + 1 ；f(5) = f(4) + 1 (5 = 4 + 1)

但我认为这不是正确的方法。有人愿意帮忙吗？

一个真正问题所在的例子：

4 的写法数：

我必须创建一个接受两个整数的方法，让它们成为nand m，并返回有多少种方法可以将m正数相加得到n。例如，像这样的方法调用partition(6, 2)应该返回 3，因为有 3 种可能的方式。它们是5 + 1、4 + 2和3 + 3。顺便说一句，4 + 2与 相同2 + 4，因此该方法不应将它们视为两个不同的变体。有人知道问题的解决方案吗？

更新：n并且m不大于 150。

考虑以下整数分区代码：

如果我以 p(7,3) 为例，函数变为 p(7,0) & p(4,3) 后会发生什么？

我一直在编写代码来迭代地划分整数并使用以前的结果来完全划分数字，我的想法是使用以前的分区可以提高速度。到目前为止，我的性能比递归地对整数进行分区慢了 22 倍，并且由于快速耗尽内存而无法测试更大的数字。如果有人可以帮助优化代码，我将不胜感激。

考虑向量s如下：

现在给定s一个固定的长度m，我想为所有可能的长度排列提供一个矩阵，m使得矩阵的每一行总和为1（不包括蛮力方法）。

例如，如果m=4（即列数），所需的矩阵将是这样的：

每个正整数 n 有 2^(n−1) 个不同的成分。如果我想要仅在我的列表中具有特定数字的组成数量：

例如 4 的组成是

但是如果我想要只有 1 和 2 的 4 的组合数，我该如何计算不同组合的数量？

编辑： 这里是计算数字的Haskell代码，但我认为即使我为数字70添加记忆也需要很长时间

这个问题类似于我几个月前的一个问题：Generating a numpy array with all combination of numbers that sum than a given number。在那个问题中，我想生成所有总和最多为常数的数字，因为每个元素都有一个最大值。

这一次，我想计算总和恰好等于该常数的所有排列。这可以看作是计算整数分区的唯一排列，其中每个元素都有一定的最大值。最终结果应该存储在一个 numpy 数组中。

使用生成器，one liner 实现了我们想要的：

给予

K=20当和时，我的性能很慢maxRange = [20]*6。排列的数量被限制为 53130，但它已经需要 20 秒。我的直觉告诉我，这应该花费不到一秒钟的时间。

有没有人有更快的解决方案？我无法修改我之前的问题的解决方案来解决这个问题，因为我不知道如何切断不再可能完全加起来的排列K。

我不介意使用@jitnumba 运算符的解决方案......只要它们比我现在拥有的更快！

提前致谢。

我需要以下算法：

• 我得到了一个指定的目标总和n和一个指定的限制m。它们都是正整数。
• 我想找到一个目标总和n的整数分区，它的总和尽可能少。
• 每个和必须小于或等于限制m。
• 在上述限制条件下，加法应尽可能靠近；也就是说，我希望n尽可能均匀地分区。

因此，例如，如果目标和是n  = 80 并且每个被加数必须最多为m  = 30，那么我至少需要三个被加数，并且最偶数分区是26 + 27 + 27。

我将如何计算？

我正在尝试实现一个程序，该程序返回整数 n 的现有分区数作为分配的一部分。我写了下面的代码，但是它返回了错误的数字（Partitions n 返回了 Partitions n-1 的结果）。我不明白为什么会这样。我已经尝试了很多东西，但仍然不知道如何解决它，有人可以帮助我吗？

m 代表分区中允许的最大数，因此 partition(4,4) 将是 5 = 4, 3+1, 2+2, 2+1+1, 1+1+1+1，但是 partition (4 ,1) 将是 1 = 1+1+1+1。执行：java Partitions n