求属性集的闭包和函数依赖的闭包算法(二)

前端之家收集整理的这篇文章主要介绍了求属性集的闭包和函数依赖的闭包算法(二)前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

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

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

猜你在找的设计模式相关文章