当当当当~求属性集的闭包和函数依赖的闭包算法第二弹！

上次的求属性集的闭包和函数依赖的闭包算法还没写完，只写玩了第一问求指定元素的闭包，今天终于又把第二问求函数依赖F的闭包写完了，先举个例子吧

R=ABC,F={A→B,B→C},求F+

解： F+ ={A→Φ,AB→Φ,AC→Φ,ABC→Φ,B→Φ,C→Φ,
A→A,AB→A,AC→A,ABC→A,B→B,C→C,
A→B,AB→B,AC→B,ABC→B,B→C,
A→C,AB→C,AC→C,ABC→C,B→BC,
A→AB,AB→AB,AC→AB,ABC→AB,BC→Φ,
A→AC,AB→AC,AC→AC,ABC→AC,BC→B,
A→BC,AB→BC,AC→BC,ABC→BC,BC→C,
A→ABC,AB→ABC,AC→ABC,BC→BC}

就是这个格式，一开始看到了这个输出我真是被吓到了。。上课时老师说求这个函数依赖的闭包问题是一个NP问题，从上面我们就可以看出来了，其中求的时候包括了很多次的求子集，求一个集合的全部子集，这听上去就有点恐怖啊，假如说一个集合有10个元素，那这个集合的子集就是2^10的也就是1024个，这是一个指数级，也就是有N个元素的话就是有2^N个子集，哈哈，好多啊。但是还是最终把程序写出来了。

我这个程序的思路很简单，但也许可能比较繁琐，若你们谁有更好的方法介绍一下吧！好了，现在就先说说这个程序的思路吧。

首先，在上一篇（一）中的成果下，我们能够求出相应的元素的闭包，然后再添加几个函数就行，其中一个是求子集函数，就是将一个集合的子集全部求出来，我用的是将个数转换为二进制如0001,0010....来分辨不同的元素，进而求出子集，这个方法可能有点繁琐，但将就用用还是可以的。另一个就是输出函数了，具体的在代码中有比较详细的注释。

下面就是代码部分啦，用java写的，当然也可以用其他语言写，如python之类的写也比较简单。（代码写的时候没怎么规划，想到点就写点，主函数有点多，但还好啦）

import java.util.*;


public class Closures {
	
	public void introduction()
	{
		System.out.println("使用方法说明:");
		System.out.println("输入集合时就可以直接abcdefg...的输入");
		System.out.println("闭包依赖的输入格式为a->b然后回车,再输入c->d，以此类推");
		System.out.println("集合中的空集以@代替");
		System.out.println("-----------------------------------------");
		
	}
	
	public void inputList(List list)//输入总的集合元素
	{
		System.out.println("请输入你的属性列,输入end结束");
		Scanner in=new Scanner(System.in);
		while(in.hasNext())
		{
			String str=in.nextLine();
			if(str.toLowerCase().equals("end"))
			{
				break;
			}
			for(int i=0;i<str.length();i++)//依次取出放入List
			{
				String s=str.substring(i,i+1).toUpperCase();
				if(!list.contains(s))
				{
					list.add(s);
				
				}
			}
		}
	}
	
	public String outputList(List list)//输出输入的集合的元素
	{
		String result="";
		System.out.println("你输入的集合为");
		for(int i=0;i<list.size();i++)
		{
			System.out.print(list.get(i));
			result+=list.get(i);
		}
		System.out.println();
		return result;
	}
	
	public void printout(Map map) //输出关系依赖的函数
	{
		Set set=map.keySet();//获取Map集合中的key对象集合
		Iterator it=set.iterator();//创建遍历器
		System.out.println("保存的依赖为:");
		while(it.hasNext()){
			String str=(String)it.next();
			String name=(String)map.get(str);//遍历Map集合
			System.out.println(str+"->"+name);
		}
	}
	
	public String add(String name,String result)//无重复的添加元素到result中
	{
		String str=result;
		for(int i=0;i<name.length();i++){
			if(result.indexOf(name.charAt(i))==-1){
				str=str+name.substring(i,i+1);
			}
		}
		return str;
	}
	
	public String calculate(String result,Map map)//计算闭包，一个递归函数
	{
		boolean flag=true;
		String comp;//比较是否增加了闭包
		Set set=map.keySet();
		Iterator it=set.iterator();
		while(it.hasNext()){
			flag=true;
			String str=(String)it.next();
			String name=(String)map.get(str);
			int i=0;
			for(i=0;i<str.length();i++)//判断str是否在result中
			{
				if(result.indexOf(str.charAt(i))==-1){
					flag=false;
					break;
				}
			}
			if(flag==true)//如果在的话就把对应的右边的值五重复的加入result
			{
				comp=result;
				result=add(name,result);
				if(result!=comp){
					result=calculate(result,map);//运用了递归，如果有所改变的话就递归的再次重新扫一遍进行计算，另外，返回值result一定要写，否则就直接退出程序了。
				}
			}
		}
		
		return result;
	}
	
	public void calculateSet(String result,String str[])//计算出所有的子集
	{
		int length=result.length();
		double max=Math.pow(2.0,length);
		for(int i=0;i<(int)max;i++)
		{
			str[i]=switchArray(i,result);
		}		
	}
	
	public String switchArray(int num,String result)//讲整数转换为二进制，进而输出所有子集
	{
		String binary=Integer.toBinaryString(num);
		boolean flag=true;//判断是否为空子集
		int count=binary.length();
		String out="";
		int length=result.length();
		char temp[]=new char[length];
		for(int i=length-1,j=count-1;i>=0;i--,j--)
		{
			temp[i]='0';
			if(j>=0&&binary.charAt(j)=='1')
			{
				temp[i]='1';
				flag=false;
			}
			
		}
		for(int i=0;i<length;i++)
		{
			if(temp[i]=='1')
			{
				out=out+result.charAt(i);
			}
		}
		if(flag==true)
		{
			out="@";
		}
		return out;
	}
	
	public static void main(String[] args)//主函数
	{	
		String result="";//定义一个存储闭包的字符串
		Closures Clo=new Closures();//创建实例
		
		Clo.introduction();//介绍使用方法
		List list=new ArrayList();//创建数列
		Clo.inputList(list);//输入集合
		Clo.outputList(list);//输出集合
		Map map=new HashMap();//由HashMap实现Map对象
		int rely=0;//计算输入了几个依赖
		
		System.out.println("请输入依赖,输入end结束输入!");
		while(true)//循环输入依赖
		{
			Scanner in=new Scanner(System.in);
			String str=in.nextLine();//扫描器执行当前行
			if(str.toLowerCase().equals("end"))//匹配结束符
			{
				break;
			}
			String s[]=str.split("->");//分割字符串将符号左边的放入KEY，右边的放入VALUE
			if(s.length==2){
				map.put(s[0].toUpperCase(),s[1].toUpperCase());//将每个函数依赖以值对的形式存入HashMap中
				rely++;
			}
		}
		Clo.printout(map);//输入依赖关系
		System.out.println("请输入所要求的闭包!输入end结束输入");
		while(true)//输入所求的闭包
		{
			Scanner in=new Scanner(System.in);
			result=in.nextLine().toUpperCase();
			if(result.toLowerCase().equals("end"))
			{
				break;
			}
			result=Clo.calculate(result,map);//计算所求的闭包
			System.out.println("所要求的闭包为:"+result);
		}
		
		//求函数依赖的闭包
		result=Clo.outputList(list);//过去开始输入的集合
		int length=(int)Math.pow(2.0,result.length());//计算集合一共有多少个子集
		String str[]=new String[length];//用来存储字符
		Clo.calculateSet(result,str);
		for(int i=0;i<length;i++)
		{
			if(str[i].indexOf('@')!=-1)//若是空集的话就不输出关系
			{
				continue;
			}
			//System.out.println(str[i]);
			result=Clo.calculate(str[i],map);//同上，为了输出闭包，先求出开始的集合的子集，再在子集中求出闭包，然后求出闭包的子集，分别输出所有的闭包
			int subLength=(int)Math.pow(2.0,result.length());
			String substr[]=new String[subLength];
			Clo.calculateSet(result,substr);
			for(int j=0;j<subLength;j++)
			{
				System.out.println(str[i]+"->"+substr[j]);//输出
			}
		}
		
		
	}
}