整数划分

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

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

整数划分－限个数

在上面的题目上加一个限制：等号右面的必须是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>
10	void PartitionIntToFixedParts(int n, int m, F &f) {
11	assert(n >= m)(static_cast <bool> (n >= m) ? void (0) : __assert_fail ("n >= m", __builtin_FILE (), __builtin_LINE (), __extension__ __PRETTY_FUNCTION__));
12	assert(m >= 2)(static_cast <bool> (m >= 2) ? void (0) : __assert_fail ("m >= 2", __builtin_FILE (), __builtin_LINE (), __extension__ __PRETTY_FUNCTION__));
13	// Set all the elements to 1
14	// 数组a里的元素永远保证按照从大到小排列
15	std::vector<int> a(m + 1, 1);
16	a[0] = n - m + 1;
17	// Set the last one to -1
18	a.back() = -1;
19
20	while (true) {
21	// 访问当前数组
22	f(a.data(), a.data() + m);
23	// 如果第一个元素和第二个元素之间的差值大于1
24	if (a[1] < a[0] - 1) {
25	// 把第一个元素减少1
26	--a[0];
27	// 把第二个元素增加1
28	++a[1];
29	// 于是现在就是一个有效的序列
30	continue;
31	}
32	// 下面是更一般的情形，需要一直往后找一个足够小的元素
33	int j = 2;
34	int s = a[0] + a[1] - 1;
35	// 因为a的末尾有一个多余的哨兵元素，所以下面的for-loop不会是死循环（一定能找到一个足够小的元素）
36	for (; a[j] >= a[0] - 1; ++j) {
37	s += a[j];
38	}
39	// 如果找到的是哨兵元素，退出循环
40	if (j >= m) break;
41	// 把找到元素增加1
42	int x = a[j] + 1;
43	a[j] = x;
44	// 把a[j]左边的元素修改成至少和a[j]一样大
45	--j;
46	while (j >= 1) {
47	a[j] = x;
48	s -= x;
49	--j;
50	}
51	a[0] = s;
52	}
53	}

用生成函数进行计数

假设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}}$ 是等价的。

整数划分

以字典序列出所有可能性

整数划分 － 不限个数

整数划分 － 限个数

用生成函数进行计数

整数划分－不限个数

整数划分－限个数