第一种方法：
/*
- 全组合
- 排列组合算法用途广泛, 需要掌握, 为降低门槛, 本文主要关注算法的逻辑和简易性, 未重视算法效率. 结合网络书本上的实现和自己的需求, 这里列有四个目标:
- 所有元素的全排列: ab的全排列是ab, ba(顺序相关);
- 所有元素的全组合: ab的全组合是a, b, ab(顺序无关);
- 求n个元素中选取m个元素的组合方式有哪些: abc中选2个元素的组合是ab, ac, bc;
- 求n个元素中选取m个元素的排列方式有哪些: abc中选2个元素的排列是ab, ba, ac, ca, bc, cb;
可以发现, 求n个元素中选取m个元素的排列方式其实是在求出n个元素中选取m个元素的组合方式后, 对每个组合组成的元素集(数组)做全排列
*/
public class Combination {
public static void Combinationg(char[] c){
char[] subchars = new char[c.length]; //存储子组合数据的数组
//全组合问题就是所有元素(记为n)中选1个元素的组合, 加上选2个元素的组合...加上选n个元素的组合的和
for (int i = 1; i <=c.length; i++) {
combination(c, c.length, i, subchars, i);
}
}
/**
* n个元素选m个元素的组合问题的实现. 原理如下:
* 从后往前选取, 选定位置i后, 再在前i-1个里面选取m-1个.
* 如: 1, 2, 3, 4, 5 中选取3个元素.
* 1) 选取5后, 再在前4个里面选取2个, 而前4个里面选取2个又是一个子问题, 递归即可;
* 2) 如果不包含5, 直接选定4, 那么再在前3个里面选取2个, 而前三个里面选取2个又是一个子问题, 递归即可;
* 3) 如果也不包含4, 直接选取3, 那么再在前2个里面选取2个, 刚好只有两个.
* 纵向看, 1与2与3刚好是一个for循环, 初值为5, 终值为m.
* 横向看, 该问题为一个前i-1个中选m-1的递归.
*/
public static void combination(char[] c, int n, int m, char[] subchars,int subn) {//从n个数里面选m个
if (m == 0) { //出口
for (int i = 0; i < subn; ++i) {
System.out.print(subchars[i]);
}
System.out.println();
} else {
for (int i = n; i >= m; --i) { // 从后往前依次选定一个
subchars[m - 1] = c[i - 1]; // 选定一个后
combination(c, i - 1, m - 1, subchars, subn); // 从前i-1个里面选取m-1个进行递归
}
}
}
public static void main(String[] args){
char[] c={'a','b','c'};
Combinationg(c);
}
}
第二种方法：
- 基本思路：
求全组合，则假设原有元素n个，则最终组合结果是2^n个。
原因是：
用位操作方法：假设元素原本有：a,b,c三个，则1表示取该元素，0表示不取。故去a则是001，取ab则是011.所以一共三位，每个位上有两个选择0,1.所以是2^n个结果。
这些结果的位图值都是0,1,2....2n。所以可以类似全真表一样，从值0到值2n依次输出结果：即 000,001,010,011,100,101,110,111 。对应输出组合结果为：空,a, b ,ab,c,ac,bc,abc. 这个输出顺序刚好跟数字0~2^n结果递增顺序一样
取法的二进制数其实就是从0到2^n-1的十进制数
public static void arranges(char[] c){
int n=c.length;
int nbit=1<<n;
for(int i=1;i<nbit;i++){
System.out.println("组合数值"+i+"对应编码为：");
for(int j=0;j<n;j++){
int temp=1<<j;
if((temp&i)!=0){
System.out.print(c[j]);
}
}
System.out.println();
}
}
