整数划分

整数划分是研究这样的问题：如何将一个正整数表示成若干个正整数的和。

比如： 8=4+2+2。等式右边的数字允许重复出现。

下面我们从这样几个方面来考察：

如何以不重复的方式列出所有可能性。（Enumerate problem）
如何快速的计算出有多少种可能性。（Count problem）

比如以数字8为例，它可以拆分成以下一些数字：

8 = 8 8 = 7+1
8 = 6+2
8 = 6+1+1
8 = 5+3
8 = 5+2+1
8 = 5+1+1+1
8 = 4+4
8 = 4+3+1
8 = 4+2+2
8 = 4+2+1+1
8 = 4+1+1+1+1
8 = 3+3+2
8 = 3+3+1+1
8 = 3+2+2+1
8 = 3+2+1+1+1
8 = 3+1+1+1+1+1
8 = 2+2+2+2
8 = 2+2+2+1+1
8 = 2+2+1+1+1+1
8 = 2+1+1+1+1+1+1
8 = 1+1+1+1+1+1+1+1

上面一共有22行。我们用函数p(n)代表正整数n有多少种拆分。于是就有：
p(1) = 1, p(2) = 2, p(3) = 3, p(4) = 5, p(5) = 7, p(6) = 11，p(10) = 42, p(100) = 190569292。

然后我们会对这个问题做一些扩展。比如：

限制等式右边的数字的个数必须是k
限制等式右边的数字必须来自于某个集合（coin exchange problem）
限制等式右边的数字必须都是奇数
限制等式右边的数字不允许重复（这个问题与上面的问题3等价）

以字典序列出所有可能性

Donald Knuth在TAOCP的7.2.1.2节对所有此类问题给出了一个一般的框架。假设我们有一个序列 $a_{1}, a_{2}, \dots, a_{n}$ , 我们可以按照下面的步骤生成它的下一个排列：

Find the largest j such that $a_{j}$ can be increased.
Incrase $a_{j}$ by the smallest fesible amount
Find the lexicographically least way to extend the new $a_{1}, \dots, a_{j}$ to a complete pattern.

整数划分－不限个数

在这个问题上，我们可以把排序函数反过来，按照字典逆序的方式生成，这样会更简单一些。

套用到前面的算法框架中就是：

Find the largest j such that $a_{j}$ can be increased: 从右往左找，找到第一个不是1的数字。
Incrase $a_{j}$ by the smallest fesible amount: 把找到的数字减去1.
Find the lexicographically least way to extend the left sequence: 用贪婪算法把剩余的部分补齐。先尝试把 $a_{j}$ 往右尽可能的smash。然后尝试 $a_{j} - 1, a_{j} - 2, \dots, 1$ 。直到整个新数组的和达到我们的目标为止。

代码如下：

1	#include <vector>
2
3	// F's signature is "void(const int* begin, const int* end)"
4	template <typename F>
5	inline void PartitionInt(int n, F&& f) {
6	// Set all the elements to 1
7	std::vector<int> a(n + 1, 1);
8	// Set the first one to zero
9	a[0] = 0;
10	// Now the sum of all the elements in vector a is n
11	int m = 1;
12	int q;
13	while (true) {
14	// Set the last number to n
15	a[m] = n;
16	// If the last number is 1, let q points to the next to last number.
17	// Else, q points to the last number
18	q = m - (n == 1 ? 1 : 0);
19
20	while (true) {
21	f(a.data() + 1, a.data() + 1 + m);
22	if (a[q] != 2) break;
23	// Break 2 to 1 + 1
24	a[q] = 1;
25	--q;
26	++m;
27	}
28
29	if (q == 0) {
30	break;
31	}
32	// Decrease a[q] by 1
33	int x = a[q] - 1;
34	a[q] = x;
35	n = m - q + 1;
36	m = q + 1;
37	while (n > x) {
38	a[m++] = x;
39	n -= x;
40	}
41	}
42	}

整数划分－限个数

在上面的题目上加一个限制：等号右面的必须是k个数字。

这次我们依然是按照降序的方式列出所有可能性。但是与上述算法不同的是：本算法从左往右寻找第一个应该被减少的元素。

1	/**
2	* @brief PartitionIntToFixedParts Divide integer `n` into m parts.
3	* @param n
4	* @param m
5	* @param f Template F's signature is void(const int begin, const int end)
6	*/
7	#include <cassert>
8	#include <vector>
9	template <typename F> void PartitionIntToFixedParts(int n, int m, F &f) {
10	assert(n >= m)(static_cast <bool> (n >= m) ? void (0) : __assert_fail ("n >= m", "/tmp/temp.cpp", 10, __extension__ __PRETTY_FUNCTION__ ));
11	assert(m >= 2)(static_cast <bool> (m >= 2) ? void (0) : __assert_fail ("m >= 2", "/tmp/temp.cpp", 11, __extension__ __PRETTY_FUNCTION__ ));
12	// Set all the elements to 1
13	// 数组a里的元素永远保证按照从大到小排列
14	std::vector<int> a(m + 1, 1);
15	a[0] = n - m + 1;
16	// Set the last one to -1
17	a.back() = -1;
18
19	while (true) {
20	// 访问当前数组
21	f(a.data(), a.data() + m);
22	// 如果第一个元素和第二个元素之间的差值大于1
23	if (a[1] < a[0] - 1) {
24	// 把第一个元素减少1
25	--a[0];
26	// 把第二个元素增加1
27	++a[1];
28	// 于是现在就是一个有效的序列
29	continue;
30	}
31	// 下面是更一般的情形，需要一直往后找一个足够小的元素
32	int j = 2;
33	int s = a[0] + a[1] - 1;
34	// 因为a的末尾有一个多余的哨兵元素，所以下面的for-loop不会是死循环（一定能找到一个足够小的元素）
35	for (; a[j] >= a[0] - 1; ++j) {
36	s += a[j];
37	}
38	// 如果找到的是哨兵元素，退出循环
39	if (j >= m) break;
40	// 把找到元素增加1
41	int x = a[j] + 1;
42	a[j] = x;
43	// 把a[j]左边的元素修改成至少和a[j]一样大
44	--j;
45	while (j >= 1) {
46	a[j] = x;
47	s -= x;
48	--j;
49	}
50	a[0] = s;
51	}
52	}

用生成函数进行计数

假设H是一个由正整数组成的集合。对于给定的某个正整数n，我们需要把n拆分成H里面的一些数字的和。用p(“H”, n)代表有多少种可能性。那么我们定义如下生成函数：

f (q) = \sum_{n > = 0} p (“ H ”, n) q^{n}

于是我们有：

f (q) = \prod_{n \in H} (1 - q^{n})^{- 1}

举个例子，对于硬币兑换问题，假设我们有2分，3分，5分三种硬币，求有多少种可能性能组成面值n。那么对应的生成函数就是：

f (q) = \frac{1}{(1 - q^{2}) (1 - q^{3}) (1 - q^{5})}

在此基础上做扩展，如果我们限制拆分后每个数字出现的次数为d。并定义这样的拆分的数量为： $p (“ H ” (\leq d), n)$ ，那么我们就有：

f (q) = \sum_{n > = 0} p (“ H ” (\leq d), n) q^{n}

用类似的推导，我们可以得到： $ $f_{d} (q) = \prod_{n \in H} (1 + q^{n} + \dots + q^{d n})$ $

等式右边是一个有限项的等比数列（比例为 $q^{n}$ ），于是有：

f_{d} (q) = \prod_{n \in H} \frac{1 - q^{(d + 1) n}}{1 - q^{n}}

在这个基础上我们可以证明：“把n拆分成奇数的和” 与“把n拆分成不重复的整数的和” 是等价的。因为“把n拆分成奇数的和”对应的生成函数是：

f (q) = \prod_{n = 1}^{\infty} (1 - q^{2 n - 1})^{- 1}

“把n拆分成不重复的整数的和” 对应着上面d=1的情况，即它的生成函数是：

f (q) = \prod_{n = 1}^{\infty} \frac{1 - q^{2 n}}{1 - q^{n}}

上面式子的分子含有q的所有偶数项。分母含有q的所有奇数及偶数项。所以把相同的项消掉后，下面就只剩奇数项。于是 $\prod_{n = 1}^{\infty} \frac{1 - q^{2 n}}{1 - q^{n}}$ 和 $\prod_{n = 1}^{\infty} \frac{1}{1 - q^{2 n - 1}}$ 是等价的。

整数划分

以字典序列出所有可能性

整数划分 － 不限个数

整数划分 － 限个数

用生成函数进行计数

整数划分－不限个数

整数划分－限个数