<分区>
一个正整数n的划分是一个非递增的正整数数组
a[1] , a[2] , ... , a[m]
满意
a[1] + a[2] + ... +a[m] = n.
m 称为此分区的长度。
我们可以按照指定的顺序列出 n 的所有分区。例如,如果我们使用规则 词典编纂法对所有英文单词进行排序,称为词典编排顺序。另一种方式,如果我们使用C语言比较字符串的规则,它被称为反向词典顺序。还有colex订单。
为了生成整数 n 的所有分区,我们有一个由 Stojmenovic 提出的很好的算法,它已经包含在 Knuth 的书中。
要生成n的所有长度正好为m的分区,我们可以使用colex序,这个算法也包含在Knuth的书中。
要生成所有元素不超过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的逆向划分!