怀化火车站网站,镇江润州区建设局网站,长春专业网站建设,wordpress 主题 瀑布流我们在笔试面试过程中经常会遇到关于排列与组合的问题#xff0c;其实这些可以通过递归简单的实现#xff0c;看下面两个例子#xff1a; #xff08;1#xff09;关于字符串排列的问题 输入一个字符串#xff0c;打印出该字符串中字符的所有排列。例如输入字符串abc其实这些可以通过递归简单的实现看下面两个例子 1关于字符串排列的问题 输入一个字符串打印出该字符串中字符的所有排列。例如输入字符串abc则输出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。 可以这样想固定第一个字符a求后面两个字符bc的排列。当两个字符bc的排列求好之后我们把第一个字符a和后面的b交换得到bac接着我们固定第一个字符b求后面两个字符ac的排列。现在是把c放到第一位置的时候了。记住前面我们已经把原先的第一个字符a和后面的b做了交换为了保证这次c仍然是和原先处在第一位置的a交换我们在拿c和第一个字符交换之前先要把b和a交换回来。在交换b和a之后再拿c和处在第一位置的a进行交换得到cba。我们再次固定第一个字符c求后面两个字符b、a的排列。这样写成递归程序如下 public class Permutation { public static void permutation(char[]ss,int i){ if(ssnull||i0 ||iss.length){ return; } if(iss.length){ System.out.println(new String(ss)); }else{ for(int ji;jss.length;j){ char tempss[j];//交换前缀,使之产生下一个前缀 ss[j]ss[i]; ss[i]temp; permutation(ss,i1); tempss[j]; //将前缀换回来,继续做上一个的前缀排列. ss[j]ss[i]; ss[i]temp; } } } public static void main(String args[]){ char []ss{a,c,b,d}; permutation(ss,0); }
} 2关于组合的问题 输入一个字符串输出该字符串中字符的所有组合。举个例子如果输入abc它的组合有a、b、c、ab、ac、bc、abc。 假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符我们有两种选择一是把这个字符放到组合中去接下来我们需要在剩下的n-1个字符中选取m-1个字符二是不把这个字符放到组合中去接下来我们需要在剩下的n-1个字符中选择m个字符。这两种选择都很容易用递归实现。 import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
public class Combination { public static void combiantion(char chs[]){ if(chsnull||chs.length0){ return ; } ListCharacter listnew ArrayList(); for(int i1;ichs.length;i){ combine(chs,0,i,list); } } //从字符数组中第begin个字符开始挑选number个字符加入list中 public static void combine(char []cs,int begin,int number,ListCharacter list){ if(number0){ System.out.println(list.toString()); return ; } if(begincs.length){ return; } list.add(cs[begin]); combine(cs,begin1,number-1,list); list.remove((Character)cs[begin]); combine(cs,begin1,number,list); } public static void main(String args[]){ char chs[]{a,b,c}; combiantion(chs); }
} 转载于:https://www.cnblogs.com/longhs/archive/2013/06/14/3135433.html
