当当当当~求属性集的闭包和函数依赖的闭包算法第二弹!
上次的求属性集的闭包和函数依赖的闭包算法还没写完,只写玩了第一问求指定元素的闭包,今天终于又把第二问求函数依赖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]);//输出 } } } }