集合划分的总划法
题目：
n个元素的集合{1,2,.,n }可以划分为若干个非空子集。
例如，当n=4 时，集合{1,2,3,4}可以划分为15个不同的非空子集如下：
{1}，{2}，{3}，{4}}， {{1，2}，{3}，{4}}，
{{1，3}，{2}，{4}}， {{1，4}，{2}，{3}}，
{{2，3}，{1}，{4}}， {{2，4}，{1}，{3}}，
{{3，4}，{1}，{2}}， {{1，2}，{3，4}}，
{{1，3}，{2，4}}， {{1，4}，{2，3}}，
{{1，2，3}，{4}}， {{1，2，4}，{3}}，
{{1，3，4}，{2}}， {{2，3，4}，{1}}，
{{1，2，3，4}}
设计出一个算法计算出n个集合可以划分的总数
思路分析：假设把集合划分为3个子集
那么加入第n个数是一个子集那么和f(n-1,2)组成f(n,3)的一种情况，
另外一种情况是往f(n-1,3)中的任意一个子集中插入。
所以f(n,m) = f(n-1,m-1)+m*f(n-1,m)
代码如下
public static void main(String[] args) {
int count =0;
int n=16;
for(int i=1;i<=n;i++){
count = count + getPartitionNum(n, i);
}
System.out.println("集合数量为"+ n + "可划分的子集组成等于全集的划法有 " + count);
}
/**
* 划分的个数
* @param n 总数量
* @param m 划分的子集个数
* @return
*/
public static int getPartitionNum(int n,int m){
if(n<m){
return 0;
}
if(n==1 || m==1 || n==m){
return 1;
}else{
return getPartitionNum(n-1, m-1) + m*getPartitionNum(n-1, m);
}
}
运行结果：
集合数量为16可划分的子集组成等于全集的划法有 1890207555
