1. 定义
排列：从给定个数的元素中取出指定个数的元素进行排序
组合：从给定个数的元素中取出指定个数的元素，不考虑排序
2. 两个的关系
排列包含了组合的过程，从给定个数的元素中取出指定个数元素（组合），然后再把取出的元素进行排序。
这意味着，我们利用组合得到组合数，然后利用组合数实现全排列，就得到了排列。
一般组合指的是取出1~n个元素的组合，因为全组合只有一个
3. 字符串的排列组合算法
3.1 不含重复字符的组合
题目描述
输入一个长度为n的字符串，输出该字符串中字符的所有组合
举例说明
如果输入"abc"，它的组合有a、b、c、ab、ac、bc、abc
算法思路
①假设在长度为n的字符串中求m个字符的组合
②从头扫描字符串的第一个字符，有两种选择：
(1)把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选取m-1个字符
(2)不把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选择m个字符
注意：所有字符取出摆放的位置都是以原来的相对位置，不改变原来的前后顺序
代码实现
public static void combiantion(char chs[]){
if(chs.length == 0) return ;
Stack<Character> stack = new Stack<Character>();
for(int i = 1; i <= chs.length; i++){
combine(chs, 0, i, stack);
}
}
//从字符数组中第begin个字符开始挑选number个字符加入list中
public static void combine(char[] chs, int begin, int number, Stack<Character> stack){
if(number == 0){ //边界条件是number取0个，则输出结果
System.out.println(stack.toString());
return ; //防止死循环
}
if(begin == chs.length) return; //边界条件为错误情况则返回，因为begin已经到最后一个字符之外，根本没有这个索引
//stack压入一个元素，表示取此字符，然后begin+1表示在此字符后面取number-1个字符，刚好②-(1)中的情况
stack.push(chs[begin]);
combine(chs, begin + 1, number - 1, stack);
stack.pop();
//刚才压入栈中的元素弹出，表示不取当前begin位置的字符，从begin+1以后取出number个字符，刚好是②-(2)中的情况
combine(chs, begin + 1, number, stack);
}
位运算实现[5][6]
基本思路：求组合，表示可以取少于总字符个数的字符组合，因为全字符组合就一个，则假设输入字符个数为n个，则最终组合结果是(2^n - 1)个。
原因：假设字符为a,b,c，则1表示取c元素，0表示不取c。所以001表示取c，010取b，100取a，011取bc.所以一共三位，每个位上有两个选择0,1.所以是(2^n - 1)个结果。依次表示为：001,010,011,100,101,110,111。对应输出组合结果为：a, b ,ab,c,ac,bc,abc.
注意：这个思路也非常好~ 但是前提是字符长度不超过32个
public static void Combination( ) {
String[] str = {"a" , "b" ,"c"};
int n = str.length; //元素个数。
int nbit = 1<<n; // “<<” 表示 左移:各二进位全部左移若干位，高位丢弃，低位补0。求出位图全组合的结果个数：2^n - 1
System.out.println("全组合结果个数为："+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 ;
if((tmp & i)!=0) { //& 表示与。两个位都为1时，结果才为1
System.out.print(str[j]); //这里是一次打印一个字符，而不是一次性打印出abc三个字符,print()而不是println()
}
}
System.out.println();
}
}
3.2 含重复字符的组合
利用hashSet实现查重：第一次放入到hashSet输出结果，如果遇到已经在hashSet中存在，则不输出结果
注意:由于利用HashSet实现去重，而不是直接在算法上实现去重，增加了空间复杂度和时间复杂度，所以不是最优算法。关于算法优化，有待后面继续提高和实现！
如果网友有更好的方法，还是多多指教！
代码实现
public static void combiantion(char chs[]){
if(chs.length == 0) return ;
HashSet<String> hashSet = new HashSet<String>();
Stack<Character> stack = new Stack<Character>();
for(int i = 1; i <= chs.length; i++){
combine(chs, 0, i, stack, hashSet);
}
}
//从字符数组中第begin个字符开始挑选number个字符加入list中
public static void combine(char[] chs, int begin, int number, Stack<Character> stack, HashSet<String> hashSet){
String s = stack.toString();
if(number == 0 && !hashSet.contains(s)){ //边界条件是number取0个，则输出结果
System.out.println(s);
hashSet.add(s);
return ;
}
if(begin == chs.length) return; //边界条件为错误情况则返回，因为begin已经到最后一个字符之外，根本没有这个索引
//stack压入一个元素，表示取此字符，然后begin+1表示在此字符后面取number-1个字符，刚好②-(1)中的情况
stack.push(chs[begin]);
combine(chs, begin + 1, number - 1, stack, hashSet);
stack.pop();
//刚才压入栈中的元素弹出，表示不取当前begin位置的字符，从begin+1以后取出number个字符，刚好是②-(2)中的情况
combine(chs, begin + 1, number, stack, hashSet);
}
3.3 不含重复字符的排列
题目描述
输入一个长度为n的字符串，输出该字符串中字符的全排列
举例说明
如果输入“abc”，则全排列为abc、acb、bac、bca、cab和cba。
算法思路
①递归实现，每递归一次取一个字符作为当前输入字符的首字符。例如，输入“abc”，则取第一个字符“a”，把字符“a”与第一个字符“a”交换，当前不用交换。剩下的字符“bc”，下次递归也是这样。如果选取的是字符“b”，则在字符数组中把字符“b”与字符“a”交换，后面选取字符就是在“ac”中选取。如果选取的是字符“c”，与字符“a”交换，下次选取就是在“ba”中选取
②每次选取后，下次递归则需要把交换的字符顺序，重新返回。
代码实现
static void permutation(char[] arr, int index, int size) {
if (index == size) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
else {
for (int i = index; i < size; i++) {
if(i != index && arr[i] == arr[index])
continue;
swap(arr, i, index);
permutation(arr, index+1, size);
swap(arr, i, index);
}
}
}
static void swap(char[] arr, int idx1, int idx2) {
char temp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = temp;
}
3.4 含有重复字符的排列
题目描述
输入一个长度为n的字符串，字符中包含重复字符，输出字符的全排列
举例说明
如果输入“abb”，则全排列为abb, bab, bba
算法思路
代码实现
public class repeatAllArray {
public static void main(String[] args) {
char a[] = { 'a', 'a', 'b', 'b' };// 以这个字符数组为例
repeatAllArray array = new repeatAllArray();
array.allArray(a, 0, a.length);
}
/*
* allArray实现含有重复字符的数组的全排列 list是含重复字符的数组，i是指示当前位置的游标，length是数组长度
*/
public void allArray(char list[], int i, int length) {
if (i == length - 1) {
for (int j = 0; j < length; j++) {
System.out.print(list[j]);
}
System.out.println();
} else {
for (int j = i; j < length; j++) {
if (!isExist(list, i, j)) {
swap(list, i, j);// 交换当前值和当前位置之后的值
allArray(list, i + 1, length);// 当前位置+1，递归
swap(list, i, j);// 再交换
}
}
}
}
/*
* isExist判断j位置的字符是否已经在list[0]~list[j-1]中出现过了
* list是含重复字符的数组，i是指示当前位置的游标，j是要判断的字符的位置
*/
public boolean isExist(char list[], int i, int j) {
for (int k = i; k < j; k++) {
if (list[j] == list[k]) {
return true;
}
}
return false;
}
/*
* swap实现了数组中两个位置的值的交换 list是含重复字符的数组，i,j表示要交换的位置
*/
public void swap(char list[], int i, int j) {
char temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}
参考文献
[1]字符串的全排列和组合
[2]字符串排列和组合的JAVA实现
[3]字符串的全排列和组合算法
[4]带有重复字符的字符数组的全排列
[5]java 全组合 与全排列
[6]字符串组合——位运算
[7]java排列组合问题汇总【经典】
