Java 求集合的所有子集

递归方法调用,求解集合的所有子集。

package ch01;

import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Set; public class QuerySubSet {

  // 递归调用, 求出 Set的子集, 返回List列表
public static List<Set<Object>> Query(Set<Object> target)
{
    // 如果 target为空, 则停止递归,并且 返回的list中 包含一个空集
if(target.size() == 0)
{
List<Set<Object>> list= new LinkedList<Set<Object>>();
list.add(target);
return list;
}
     // 如果 target 中有一个元素, 那么改target的子集体包括 空集 和 自身
     else if(target.size() == 1)
{
List<Set<Object>> list= new LinkedList<Set<Object>>();
list.add(target);
Set<Object> nullset=new HashSet<Object>();
list.add(nullset);
return list;
}
// 如果 target中的元素大于 1 个,则将target分成两个新的集合,并求出两个新集合的所有子集,再将两个List子集进行合并,即可以得到target的所有子集。
else
{
Iterator<Object> iter=target.iterator();
Object elem=iter.next();
target.remove(elem);
Set<Object> newSet=new HashSet<Object>();
newSet.add(elem); List<Set<Object>> list1=Query(newSet); // 递归调用
List<Set<Object>> list2=Query(target); // 递归调用
return merge(list1, list2); // 合并两个 list
}
}

   // 合并两个list, 两次for循环遍历两个list列表。
public static List<Set<Object>> merge(List<Set<Object>> list1, List<Set<Object>> list2)
{
List<Set<Object>> mlist=new LinkedList<Set<Object>>();
for(Set<Object> set1: list1 )
for(Set<Object> set2: list2)
{
Set<Object> newSet=new HashSet();
newSet.addAll(set1);
newSet.addAll(set2);
mlist.add(newSet);
}
return mlist;
} /**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Set<Object> targ=new HashSet<Object>();
for(int i=0; i<10; i++)
{
targ.add(Integer.toString(i));
} List<Set<Object>> allsubset= QuerySubSet.Query(targ); boolean f1=true;
for(Set<Object> set1: allsubset)
{
if(!f1)
System.out.print(",");
f1=false; System.out.print("{"); boolean f2=true;
for(Object obj: set1)
{
if(!f2)
System.out.print(",");
f2=false;
System.out.print(obj.toString());
}
System.out.println("}");
} } }
上一篇:UVA 10139 Factovisors(数论)


下一篇:centos7安装java环境和maven环境