集合划分问题 java实现

集合划分问题

1.1 算法设计思想

对于 n 个元素的集合，可以划分成由 m(1<=m<=n)个子集构成的子集，如 {{1}，{2}，

{3}，{4}}就是由 4 个子集构成的非空子集。假设 f(n,m)表示将 n 个元素的集合划分成由 m

个子集构成的集合的个数，那么可以这样来看：

1)若 m==1，则 f(n,m)=1;

2)若 n==m，则 f(n,m)=1;

3)若非以上两种情况，f(n,m)可以由下面两种情况构成

f(n,m) =

f(n-1,m-1)+m*f(n-1,m) (m<n&&m!=1)

参考：http://www.cnblogs.com/dolphin0520/archive/2011/07/12/2103917.html

1.2 程序源码

Start.java

import java.io.*;

import java.util.Scanner;

import java.io.FileNotFoundException;

public class Start {

public static void main(String[] args) throws FileNotFoundException {

Partition p = new Partition();

for(int i=1;i<=num;i++){

sum += p.Partition(num, i);

}

long t2 = System.nanoTime();//结束时间

System.out.println(" 输 入 元 素 个 数 为 ： "+num+" 可 分 集 合 个 数

为："+sum);

System.out.println("本次运行时间为： "+(t2-t1)+"ns");

}