9.9再帰と動的計画（四）――ある集合のすべてのサブセットに戻る

/**
 * 機能：あるセットのすべてのサブセットを返します。
 */
3つの方法：
方法1：反復

	//  
	/**
	 *   ：               ，            。
	 * 		          moreSubsets       ，    allSubsets。
	 * @author Lynne
	 * @param set
	 * @param index
	 * @return
	 */
	public static ArrayList<ArrayList<Integer>> getSubsets2(ArrayList<Integer> set,int index){
		ArrayList<ArrayList<Integer>> allSubsets=new ArrayList<ArrayList<Integer>>();
		
		allSubsets.add(new ArrayList<Integer> ());//     
		
		while(index<set.size()){
			int item=set.get(index);
			ArrayList<ArrayList<Integer>> moreSubsets=new ArrayList<ArrayList<Integer>>();	
			
			for(ArrayList<Integer> subsets:allSubsets){
				ArrayList<Integer> newSubsets=new ArrayList<Integer>();
				newSubsets.addAll(subsets);
				newSubsets.add(item);
				moreSubsets.add(newSubsets);
			}
			allSubsets.addAll(moreSubsets);
			index++;
		}
		return allSubsets;
	}

方法二：再帰

	//   
	/**
	 *   ：     
	 * 		  P（n-1），      ，              an。
	 * @param set
	 * @param index
	 * @return
	 */
	public static ArrayList<ArrayList<Integer>> getSubsets(ArrayList<Integer> set,int index){
		ArrayList<ArrayList<Integer>> allSubsets;
		
		if(set.size()==index){//    ，     
			allSubsets=new ArrayList<ArrayList<Integer>>();
			allSubsets.add(new ArrayList<Integer>());//   
		}else{
			allSubsets=getSubsets(set, index+1);
			int item=set.get(index);
			ArrayList<ArrayList<Integer>> moreSubsets=new ArrayList<ArrayList<Integer>>();	
			
			for(ArrayList<Integer> subsets:allSubsets){
				ArrayList<Integer> newSubsets=new ArrayList<Integer>();
				newSubsets.addAll(subsets);
				newSubsets.add(item);
				moreSubsets.add(newSubsets);
			}
			allSubsets.addAll(moreSubsets);
		}		
		return allSubsets;
	}

方法の3：数学を組み合わせます。

	//    
	/**
	 *   ：    1 2^n     ，      
	 *          :1)    （“yes”）;2)     （“no”）。         yes no。
	 *    2^n   ，   yes  1，  no  0，            。
	 *   ，                    。    1 2^n     ，      。
	 * @param set
	 * @return
	 */
	public static ArrayList<ArrayList<Integer>> getSubsets(ArrayList<Integer> set){
		ArrayList<ArrayList<Integer>> allSubsets=new ArrayList<ArrayList<Integer>>();
		
		int size=1<<set.size();//       ，  2^n。
		for(int i=0;i<size;i++){
			ArrayList<Integer> subsets=new ArrayList<Integer>();
			subsets=convertIntToSet(i);
			allSubsets.add(subsets);
		}
		
		return allSubsets;
	}
	
	public static ArrayList<Integer> convertIntToSet(int x){
		ArrayList<Integer> subsets=new ArrayList<Integer>();
		for(int i=x;i>=1;i>>=1){
			if((i&1)==1)
				subsets.add(i);
		}		
		return subsets;
	}