主要内容 #

1. 问题描述
2. 算法分析
3. 编程求解

1. 问题描述 #

设S是一个具有n个元素的集合，S = {a1, a2, ···, an}，现将S划分成k个满子集合S1, S2, ···, Sk，并且满足：
1. 任意一个集合不为空；
2. 任意一个元素不可能同时存在两个子集合中；
3. 所有的元素均必须被分配。
则称S1, S2, ···, Sk是集合S的一个划分，它相当于把S集合中的n个元素a1, a2, ···, an放入k个无标号的盒子中，使得没有一个盒子为空请你确定n个元素a1, a2, ···, an，放入k个无标号的盒子中的划分数S(n,k)。
实际上这个问题的求解方法与之前的122课中第二类Stirling数求解方法完全一样。

2. 算法分析 #

先举个例子，设S={1, 2, 3, 4}, k = 3,不难看出S有6种不同的划分方案，即S(4, 3) = 6。具体方案如下：
{1,2}{3}{4}
{1,3}{2}{4}
{1,4}{2}{3}
{2,3}{1}{4}
{2,4}{1}{3}
{3,4}{1}{2}
考虑一般情况，对于任意的含n个元素的a1, a2, ···, an的集合S，放入k个无标号的盒子中去，划分数为S(n,k)，凭直觉和经验很难划分和枚举划分的所有方案，必须归纳出问题的本质。其实对于任意一个元素an，必然有以下两种情况：
1. {an}是其中一个子集，于是我们只需要把a1, a2, ···, an-1个元素划分到k-1个子集中，便解决了本题，这种强况下划分数共有S(n-1, k-1)个；
2. {an}不是k个子集中的一个，则an必须和其他元素构成一个子集。则问题相当于先把a1, a2, ···, an-1划分成k个子集，这种情况下划分数共有S(n-1, k)个；然后再把an加入到k个子集中的任意一个中去，共有k种加入其中的方法，这样对于an的每一种加入方式，都可以使集合划分为k个子集，因此根据乘法原理，划分数共有k*S(n-1, k)个。
综合上述的两种情况，应用加法原理，得到将n个元素的a1, a2, ···, an的集合S划分为k个子集合的划分数为以下的递归公式
S(n, k) = S(n – 1, k – 1) + k * S(n – 1, k)（n > k, k > 0）。
边界条件

因此，划分数S(n, k)的递归关系式为：
S(n, k) = S(n – 1, k – 1) + k * S(n – 1, k) (n > k, k > 0);
S(n, k) = 0 (n < k或k = 0);
S(n, k) = 0 (k = 1或k = n)。

3. 编程计算 #

#include < iostream >
using namespace std;

int s(int n, int k){
   if(n < k || k == 0) return 0;
   if(n == k || k == 1) return 1;
   return s(n - 1, k - 1) + k * s(n - 1, k);
}

int main(){
   int n, k;
   cin >> n >> k;
   cout << s(n, k) << endl;
   return 0;
}