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("}");

        }

    }

}