递归问题 - 黑马程序员技术交流社区

package com.libo.qusetion01;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class MyCombinationDemo {
/*
* 设有n个元素，组合数量有2的n次方种。
* 对 0 到 2的n次方-1 中的每个数，考察其二进制位形式，位数为1代表相应元素加入到组合，0则不加入该元素至组合。
*
* 取组合方法 a2^0 b2^1 c2^2
* 这样 1 只有a
* 2 b
* 3 ab
* 4 c
* 5 ac
* .......一次下去所有的都出来了
* 参数： list ---- 原始数组
* 返回：包含所有组合数组的数组
*/
public static void main(String [] args){
String [] strs=new String[]{"a","b","c"};
//集合里面放集合每个集合就是一个组合
List<List<String>> result=new ArrayList<List<String>>();
//获取所有的组合用位移的方法
getAllGroup(result,strs);
System.out.println(Arrays.toString(strs)+"----组合情况如下------");
System.out.println(result);
System.out.println("------------全排列 ---------------");
//根据获取的组合size>2的全排序
getAllSort(result);
}
private static void getAllSort(List<List<String>> result) {
//如果是全排序的肯定有很多都存入一个新的集合
List<String> resultAll=new ArrayList<String>();
for(List<String> list : result){
if(list.size()>1){
//就将其全排序
int start=0;
int last=list.size()-1;
char [] buf=new char[list.size()];
for(int i=0;i<list.size();i++){
buf[i]=list.get(i).charAt(0); //每个一个
}
List<String> listAll=new ArrayList<String>();
completeSort(buf,start,last,listAll);
resultAll.addAll(listAll); //加到里面
}
else{
resultAll.addAll(list);
}
}
//size大小排序
Collections.sort(resultAll, new MyCompBySize());
int size=1;
for(int i=0;i<resultAll.size();i++){
if(resultAll.get(i).length()!=size){
System.out.println();
size++;
}
System.out.print(resultAll.get(i)+" ");
}
}
//获取全排列
private static void completeSort(char[] buf, int start, int last, List<String> listAll) {
//最后一了直接可以输出了
if(start==last){//当只要求对数组中一个字母进行全排列时，只要就按该数组输出即可
StringBuffer sb=new StringBuffer();
for(int i=0;i<=last;i++){
sb.append(buf[i]);
}
listAll.add(sb.toString());
}
else{//多个字母全排列当原来第一个抽出来排好之后就拿到后一个与第一个换位子这时重新上一步的全排序
//全排序之后要不位子换回来不用管中间的过程只管开始的时候然后是递归
for(int i=start;i<=last;i++){
swap(buf,i,start); //每次都拿和第一个位置交换后面的就不用换后面的用递归自己会全排序的
completeSort(buf,start+1,last, listAll);//后续元素递归全排列
swap(buf,i,start);
}
}
}
private static void swap(char[] buf, int i, int start) {
char temp=buf[i];
buf[i]=buf[start];
buf[start]=temp;
}
//获得所有的组合
private static void getAllGroup(List<List<String>> result, String[] strs) {
//最大就这么大 1+2+4=7 \最大局势abc的情况
int n=(int)Math.pow(2, strs.length);
for(int i=1; i<n; i++){
//用来存入 1的情况
List<String> list=new ArrayList<String>();
for(int j=0;j<strs.length; j++){
if(((i>>>j)&1)==1){
list.add(strs[j]);
}
}
result.add(list); //组合加入最后的
}
}
}
//自定义比较器
class MyCompBySize implements Comparator<String>{
@Override
public int compare(String s1, String s2) {
return s1.length()-s2.length();
}
}

复制代码