问题标签 [integer-partition]

我试图了解整数分区表是如何工作的。然而，到目前为止，我无法创建一个。

这个查询有什么问题：

我收到此错误：

Error: PARTITION BY expression must be DATE(<timestamp_column>), a DATE column, or RANGE_BUCKET(<int64_column>, GENERATE_ARRAY(<int64_value>, <int64_value>, <int64_value>))

我想n用k分区元素计算整数分区。可能的分区元素是通过v具有不同元素的给定向量定义的。可以多次选择分区元素。我怎样才能做到这一点？不遍历n.

例子：

n := 10

k := 3

v := 1,2,6,7,8

=> 3

我想计算总和为 的a子k集元素的子集n。可能的子集元素是通过a具有不同正元素的给定数组定义的。每个子集只能选择一次可能的子集元素。我怎样才能做到这一点？在不遍历所有子集的情况下是最优的。

例子：

n := 10

k := 3

a := 1,2,6,7,8

=> 1 ( 1,2,7 )

我的程序计算 的整数分区n，它们具有k不同的分区元素，每个分区都小于或等于m。我怎样才能提高性能？我已经缓存了中间结果。

使用 GAP 4.10.2 编写的“递归分区号”代码如下。例如，您能解释一下nrparts(15)的GAP 编程的工作步骤吗？我们如何在程序中一步一步得到nrparts(15) = 176 ？

来自 codewars 的问题https://www.codewars.com/kata/52ec24228a515e620b0005ef/python

在数论和组合学中，正整数 n 的分区，也称为整数分区，是一种将 n 写为正整数之和的方式。仅在其被加数的顺序上不同的两个和被认为是相同的分区。如果顺序很重要，那么总和就变成了一个组合。例如，4 可以以五种不同的方式进行分区：

给定数字 n，编写一个函数 exp_sum(n)，它返回 n 可以划分的方式总数。例如：exp_sum(4) = 5

为什么递归方法：

与此特定方法（此 kata 的最佳解决方案）相比，运行时间要长得多？

即使使用记忆化，递归方法也几乎无法在大约 10000 毫秒的时间内通过测试用例，而上述方法需要 1000 毫秒。

谁能解释上面的特定方法是如何工作的以及它背后的逻辑，或者它是否使用了一些我可以阅读的特定算法？

我在某处在线找到了这段代码，我试图弄清楚它是如何工作的。您为 partitions() 函数提供一个整数，代码返回不包括重复数字的不同分区的数量（例如 n = 5 -> 2 个分区 (3,2) & (4,1)）。我想了解这个递归解决方案究竟是如何管理这个的。我一直在玩弄代码，跟踪递归调用，但我仍然不太明白它是如何工作的。请帮我理解。

例如，这是一个矩阵：

我想找到一些总和等于 [4, 3, 2, 1] 的行。预期的答案是行：{0,1,3,4}。因为：

是否有一些著名的或相关的算法来解决这个问题？

感谢@sascha 和@N。沃达的评论。为了澄清这一点，我在这里提供了更多细节。

在我的问题中，矩阵将有大约 50 行和 25 列。但回声行将只有少于 4 个元素（其他为零）。每个解决方案都有 8 行。

如果我尝试所有组合，c(8, 50) 大约是 5.5 亿次尝试。太复杂了。所以我想找到一个更有效的算法。

我想计算我们可以将数字划分为不同部分的方法的数量n，k其中每个部分不大于m.

因为k := 2我有以下算法：

但是我如何计算整数分区k > 2呢？通常我有n > 100000, k := 40, m < 10000.

先感谢您。

使用下面的代码，我用每个分区中的数字来计算受限整数分区（每个数字在每个分区中只能出现一次）k，每个数字等于或大于1且不大于m。此代码会生成大量缓存值，以便快速耗尽内存。

例子：

sum := 15, k := 4, m:= 10预期的结果是6

具有以下受限整数分区：

1,2,3,9, 1,2,4,8, 1,2,5,7, 1,3,4,7, 1,3,5,7,2,3,4,6

是否有避免/减少缓存的公式？或者我如何计算受限整数部分k and m？