266 集合的划分

< 1 min read

集合的划分 #

在数学中，集合S的划分是把S分割到覆盖了S的全部元素的不交叠的“部分”或“块”或“单元”中。例如：将集合S={1,2,3}的3个元素，划分成2个集合则有以下划法:

(1):S={1,2}U{3} (2):S={1,3}U{2} (3):S={2,3}U{1}

针对集合划分的问题，首先我们定义递归函数f(n,k),功能就是返回把n个元素分成k个集合的方法数，根据上面的例子我们容易知道f(3,2)=3

def f(n,k):#f(n)函数功能：返回划分集合的方法数，参数为n为集合元素的总个数，k为划分为几个集合
	pass

递归问题的拆解是递归最核心的部分，针对集合的划分，考虑一般情况，对于集合S中任意一个元素i，在划分k个子集时分为两种情况:

1.把{i}单独作为一个子集，剩下的n-1个元素划分为k-1个子集，此时有f(n-1,k-1)种

2.把除了i之外的元素划分为k个子集，即f(n-1,k),此时把i放到k个子集当中的任意一个集合即可,此时有k*f(n-1,k)种

则综合1,2两种情况，我们就得到了递归函数的数学表达式，f(n,k)=k*f(n-1,k)+f(n-1,k-1)

def f(n,k):
	s= k*f(n-1,k)+f(n-1,k-1)#递归函数地拆解
	return s

在考虑一般情况将递归问题拆解后，考虑递归的边界情况。

首先不能把n个元素不放到任何一个集合当中，即k=0时f(n,0)=0。也不能把n个元素放到多与n的集合当中,即n<k时，f(n,k)=0

其次，在式f(n-1,k)的递归调用中，随着n的减少，当n=k时，f(n,k)=1。在式f(n-1,k-1)的递归调用中n,k在同时减少，当减少到k=1时f(n,k)=1

因此上述的边界条件可总结如下：

def f(n,k):
	if(n<k or k==0):#满足边界条件，递归的出口
		return 0
	if(k==1 or k==n):#递归出口
		return 1
	s= k*f(n-1,k)+f(n-1,k-1)#递归的拆解
	return s

根据集合划分的递归算法，理解递归算法的三要素

掌握集合划分的递归算法