本帖最后由 观决 于 2014-6-10 12:22 编辑
我刚才分析了一下 就拿a b c为例子吧
刚才是 进去第一个show(0,new String())----->current_recur 判断次数吧 最多递归str.length()次
过程大概这样
1： temp 是空的 ----->!(temp.contains(str.substring(i, i + 1)))成立 ----->show(current_recur + 1, new String(temp + str.substring(i, i + 1))); current_recur +1=1
2： temp = a ------>!(temp.contains(str.substring(i, i + 1)))不成立 ---->i++一次 a不包括b -----这时候ab作为temp放进去 current_recur +1=2
3: temp= ab --------> 又从a开始遍历 发现a b 都有 c 没得 这次abc都放入 这时候 current_recur =3不满足条件 接着后面的运行 就第一次输出了abc
4: 然后这次的输出了 说明递归进来这次的完了 跳到上次递归开始的地方 这时候 temp=ab 同样输出 ab 这时候 有跳会上一级 temp=a 这时候因为这次的a值添加了b就满足条件去递归了 所以再次回来的时候 就是a里面包括c 吗这个条件 发现不包括 条件成立 以ac开始递归和上面的ab一样 同样输出acb ac
5再次回来的时候a开头的已经完了 输出a
后面就是 b开头和a 一样
我画了个图 我也只能呢过理解到这里了
顺便说我的方法 我也是问网上看了有人用全排列 有人用组合 我把他们合起来了 自己修改了一下
- 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();
- }
-
- }
|
收藏
淘帖
踩
