package com.hdwang;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by hdwang on 2016-12-29.
 * 集合中输出所有子集（空集除外），或者输出指定元素个数的子集
 * 思路：对每个元素进行标记（选择1 不选0），穷举子集，穷举中可进行筛选
 */
public class Combine2 {

    /**
     * 集合
     */
    private int data[] = {1, 2, 3, 4, 5, 6, 7, 8};

    Combine2(int size){
        //初始化集合
        this.data = http://www.mamicode.com/new int[size];
        for(int i=0;i<size;i++){
            this.data[i] = i+1;
        }
        System.out.println("集合是:"+ Arrays.toString(this.data));
    }

    /**
     * 组合子集
     */
    List<String> subColListCH = new ArrayList<String>();

    /**
     * 输出集合的所有子集（空集忽略）
     */
    public void generateAllSubCol(){
        //256表示8个元素的输出情况
        for(int i = 1; i < 256; i++)   // 2^8 = 256
        {
            System.out.print(i+ " : ");
            int mark = 1;
            for(int j = 0; j < 8; j++)
            {
                int index = mark & i;  //mark与i后 得到i的每一位
                if(0 != index)         // 该位置是1，状态是选中，则输出对应元素
                {
                    System.out.print(data[j]+ " ");
                }
                mark <<= 1;  //mark在内层循环中，每次的值为1,2,4,8,16,32,64,128
            }
            System.out.println();
        }
    }

    /**
     * 输出指定元素个数的子集
     * @param subSize 子集大小
     */
    public void generateSubCol(int subSize){
        System.out.println("子集大小是："+subSize);

        int elCount = data.length; //元素个数
        int allSubColCount = (int)Math.pow(2,elCount); //子集个数（空集不算）

        for(int i=1;i<allSubColCount;i++){ //i表示了一个子集的输出规则
            int mark = 1; //用于取出i的每一位
            List<Integer> subCol = new ArrayList(); //存储子集元素

            for(int j=0; j<elCount; j++){
                int index = mark & i; //取出i的第1位，第2位。。。
                if(0 != index){
                    subCol.add(data[j]);
                }
                mark <<= 1; //mark左移1位，用于获取i高一位的数字
            }

            if(subCol.size() == subSize){ //子集个数符合要求
                subColListCH.add(listToString(subCol, ‘,‘));
            }
        }

        System.out.println("\n打印组合集合:size is "+this.subColListCH.size());
        for(int i=0;i< this.subColListCH.size();i++) {
            String line = subColListCH.get(i);
            System.out.println(line);
        }
    }

    /**
     * list转换字符串
     * @param list list
     * @param separator 分隔符
     * @return 字符串
     */
    public String listToString(List list, char separator) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < list.size(); i++) {
            sb.append(list.get(i)).append(separator);
        }
        return sb.toString().substring(0,sb.toString().length()-1);
    }
}

Combine2 combine2 = new Combine2(3);
combine2.generateSubCol(2);