1.概述
在高中的时候经常会遇到一些排列组合的问题，那个时候基本上都是基于公式计算的。其实理论上是可以枚举出来的，而计算机最擅长的事情就是枚举，本文主要讨论a,b,c三个字符的各种排列组合问题，当字符增加的时候，思路是相同的。
2.可重复排列
可重复排列就是给定，a,b,c三个字符，组成长度为3的字符串，其中a,b,c可以使用多次。这个时候可以使用递归思想：第一个字符从a,b,c中选择一个，之后的问题转化为：a,b,c三个字符组成长度为2的字符串。控制好递归退出的条件，即可。
public class Permutation {
public static void main(String[] args) {
char[] chs = {'a', 'b', 'c'};
per(new char[3], chs, 3 - 1);
}
public static void per(char[] buf, char[] chs, int len) {
if (len == -1) {
for (int i = buf.length - 1; i >= 0; --i) {
System.out.print(buf[i]);
}
System.out.println();
return;
}
for (int i = 0; i < chs.length; i++) {
buf[len] = chs[i];
per(buf, chs, len - 1);
}
}
}
3.全排列
全排列的意思，就是只能用a,b,c三个元素，做排列，每个用且只能用一次。
也可以利用递归，第一个字符串一共有n种选择，剩下的变成一个n-1规模的递归问题。而第一个字符的n种选择，都是字符串里面的。因此可以使用第一个字符与1-n的位置上进行交换，得到n种情况，然后递归处理n-1的规模，只是处理完之后需要在换回来，变成原来字符的样子。
public class Permutations {
public static void main(String[] args) {
char[] arrs = {'a','b','c'};
List<List<Character>> results = new Permutations().permute(arrs);
for (List<Character> tempList : results){
System.out.println(String.join(",",
tempList.stream().map(s->String.valueOf(s)).collect(Collectors.toList())));
}
}
public List<List<Character>> permute(char[] nums) {
List<List<Character>> lists = new LinkedList<>();
tempPermute(nums, 0, lists);
return lists;
}
public void tempPermute(char[] nums, int start, List<List<Character>> lists){
int len = nums.length;
if(start == len-1){
List<Character> l = new LinkedList<>();
for(char num : nums){
l.add(num);
}
lists.add(l);
return;
}
for(int i=start; i<len; i++){
char temp = nums[start];
nums[start] = nums[i];
nums[i] = temp;
tempPermute(nums, start+1, lists);
temp = nums[start];
nums[start] = nums[i];
nums[i] = temp;
}
}
}
在1中使用打印的方式，这里使用返回值的方式，因为有些场景我们希望得到值并且返回。
4.组合
求所有组合也就是abc各个位是否选取的问题，第一位2中可能，第二位2种。。。所以一共有2n种。用0表示不取，1表示选取，这样可以用110这样的形式表示ab。abc一共的表示形式从0到23-1。然后按位与运算，如果结果为1就输出当前位，结果0不输出。
public class Comb {
public static void main(String[] args) {
char[] chs = {'a','b','c'};
comb(chs);
}
public static void comb(char[] chs) {
int len = chs.length;
int nbits = 1 << len;
for (int i = 0; i < nbits; ++i) {
int t;
for (int j = 0; j < len; j++) {
t = 1 << j;
if ((t & i) != 0) { // 与运算，同为1时才会输出
System.out.print(chs[j]);
}
}
System.out.println();
}
}
}
