组合-Java

二进制解决组合问题：

public class CombinationByBinary {
    public static void combination() {
        /*
         * 基本思路：求全组合，则假设原有元素n个，则最终组合结果是2^n个。原因是： 用位操作方法：假设元素原本有：a,b,c三个，则1表示取该元素，0表示不取。故去a则是001，取ab则是011.
         * 所以一共三位，每个位上有两个选择0,1.所以是2^n个结果。 这些结果的位图值都是0,1,2....2^n。所以可以类似全真表一样，从值0到值2^n依次输出结果：即： 000,001,010,011,100,101,110,111
         * 。对应输出组合结果为： 空,a, b ,ab,c,ac,bc,abc. 这个输出顺序刚好跟数字0~2^n结果递增顺序一样 取法的二进制数其实就是从0到2^n-1的十进制数
         * ****************************************************************** *
         */
        String[] str = { "a", "b", "c" };
        int n = str.length; // 元素个数。
        // 求出位图全组合的结果个数：2^n
        int nbit = 1 << n; // “<<” 表示 左移:各二进位全部左移若干位，高位丢弃，低位补0。:即求出2^n=2Bit。
        System.out.println("全组合结果个数为：" + nbit + ",二进制：" + Integer.toBinaryString(nbit));

        for (int i = 0; i < nbit; i++) { // 结果有nbit个。输出结果从数字小到大输出：即输出0,1,2,3,....2^n。
            System.out.print("组合数值  " + i + " 对应编码为： ");
            for (int j = 0; j < n; j++) { // 每个数二进制最多可以左移n次，即遍历完所有可能的变化新二进制数值了
                int tmp = 1 << j;
                System.out.println(Integer.toBinaryString(tmp) + "---");
                if ((tmp & i) != 0) { // & 表示与。两个位都为1时，结果才为1
                    System.out.print(str[j]);
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        combination();
    }
}

递归解决组合问题：

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

/**
 * 
 * <p>
 * ClassName MyCombination
 * </p>
 * <p>
 * Description 一般地，从m个不同的元素中，任取n（n≤m）个元素为一组，叫作从m个不同元素中取出n个元素的一个组合。
 * </p>
 * 
 * @author TKPad [email protected]
 *         <p>
 *         Date 2015年3月20日 下午10:45:59
 *         </p>
 * @version V1.0.0
 *
 */
public class MyCombination {
    public static void combiantion(char chs[]) {
        if (chs == null || chs.length == 0) {
            return;
        }
        List<Character> list = new ArrayList<Character>();
        for (int i = 1; i <= chs.length; i++) {
            combine(chs, 0, i, list);
        }
    }

    // 从字符数组中第begin个字符开始挑选number个字符加入list中
    public static void combine(char[] cs, int begin, int number, List<Character> list) {
        if (number == 0) {
            System.out.println(list.toString());
            return;
        }
        if (begin == cs.length) {
            return;
        }
        list.add(cs[begin]);
        combine(cs, begin + 1, number - 1, list);
        list.remove((Character) cs[begin]);
        combine(cs, begin + 1, number, list);
    }

    public static void main(String args[]) {
        char chs[] = { ‘a‘, ‘b‘, ‘c‘, ‘d‘, ‘e‘ };
        combiantion(chs);
    }
}