algorithm - 整数分割

标签 algorithm combinatorics

<分区>

一个正整数n的划分是一个非递增的正整数数组

a[1] , a[2] , ... , a[m]

满意

a[1] + a[2] + ... +a[m] = n.

m 称为此分区的长度。

我们可以按照指定的顺序列出 n 的所有分区。例如,如果我们使用规则 词典编纂法对所有英文单词进行排序,称为词典编排顺序。另一种方式,如果我们使用C语言比较字符串的规则,它被称为反向词典顺序。还有colex订单。

  1. 为了生成整数 n 的所有分区,我们有一个由 Stojmenovic 提出的很好的算法,它已经包含在 Knuth 的书中。

  2. 要生成n的所有长度正好为m的分区,我们可以使用colex序,这个算法也包含在Knuth的书中。

  3. 要生成所有元素不超过k的n的所有分区,我们可以使用1中的算法,只需改变其循环的初始条件和退出条件即可。

我的问题来了:如何生成长度恰好为m,元素不超过k的分区?

这里 m 和 k 是常量。当然,元素不超过k的划分等价于第一个元素不超过k。


哦,我想我已经解决了。对于

a[1] + a[2] + ... + a[m] = n

可以写成

(k+1-a[1]) + (k+1-a[2]) + ... + (k+1-a[m]) = m(k+1)-n

而后一个只是m(k+1)-n的逆向划分!

最佳答案

递归呢?要获得 {n,m,k} 的每个允许分区,对 [1,k] 中的每个 j 取 a[1]=j,然后是 {n-j,m-1,j} 的每个允许分区。

关于algorithm - 整数分割,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3948047/

相关文章:

python - 从一组边有效地创建和存储所有大小的所有 "valid"边组合

c - 此代码如何从任何基数阶乘中找到尾随零的数量?

algorithm - 访问网格上每个 "special"点所需的最少步数

c++ - 找到所有可能的大小为 n 的数组,这些数组是用另一个数组中所有可能的顺序的元素的所有可能组合构造的?

java - 使用某些操作找到相应的电线起点和终点所需的行程数

haskell - Haskell 中 GADT 的枚举

matlab - 将参数(即笛卡尔积)排列成多维数组

algorithm - Code Golf : Validate Sudoku Grid

r - 在 R 中计算蚕食/归因

java - 如何让数组在第一个元素上放置一个零而不跳过它?