求集合的全部子集

绝地灬酷狼 2022-06-18 11:10 164阅读 0赞

import java.util.ArrayList;
    import java.util.List;
    
    public class Main {
    
    	public static void main(String ss[]) {
    		int a[] = { 1, 2, 3 };
    		p(a);
    
    	}
    
    	/**
    	 * 集合的所有子集
    	 * 
    	 * @param s
    	 * @return
    	 */
    	public static void p(int[] data) {
    		List<List<Integer>> list = new ArrayList<List<Integer>>();
    
    		// 有a个元素的集合，一共有2^a-1个非空子集
    		int n = 1;
    		for (int i = 0; i < data.length; i++) {
    			n = n * 2;
    		}
    		n = n - 1;
    
    		// 对于每一个数字，得到其二进制表示s。取出s中为1的位置的下标，
    		// 将data数组中该下标的内容添加到临时列表tlist中，
    		// 一次内层循环添加一个元素，一次外层循环完成一个子集
    		for (int i = 1; i <= n; i++) {
    			// 取出n这个数字的位置为1的数字，组成集合
    			String s = reverse(Integer.toBinaryString(new Integer(i)));
    			List<Integer> tlist = new ArrayList<Integer>();
    			for (int j = 0; j < s.length(); j++) {
    				if (s.charAt(j) == '1') {
    					tlist.add(data[j]);
    				}
    			}
    			list.add(tlist);
    		}
    
    		// 输出子集
    		for (int i = 0; i < list.size(); i++) {
    			for (int j = 0; j < list.get(i).size(); j++) {
    				System.out.print(list.get(i).get(j) + " - ");
    			}
    			System.out.println();
    		}
    	}
    
    	/**
    	 * 将字符串倒转 abcd->dcba
    	 * 
    	 * @param s
    	 * @return
    	 */
    	public static String reverse(String s) {
    		StringBuilder builder = new StringBuilder(s);
    		for (int i = 0; i < s.length() / 2; i++) {
    			char c_1 = s.charAt(i);
    			int end = s.length() - 1 - i;
    			char c_2 = s.charAt(end);
    			builder.setCharAt(end, c_1);
    			builder.setCharAt(i, c_2);
    		}
    		return builder.toString();
    	}
    }

基本思想是：

有a个元素的集合，一共有2^a-1个非空子集。

假设说有1、2、3三个数字表示的集合，那么三个数字的非空子集一共有2^3-1=7个

二进制表示分别为：

111
    
    110
    
    101
    
    100
    
    011
    
    010
    
    001

由上面的二进制表示可以看出，取出二进制表示中的1的位置的下标，

将data数组中该下标的内容添加到临时列表tlist中，

一次内层循环添加一个元素，一次外层循环完成一个子集。