Java递归实现字符串全排列与全组合
排列组合算法用途广泛,需要掌握,为降低门槛,本文主要关注算法的逻辑和简易性,未重视算法效率.结合网络书本上的实现和自己的需求,这里列有四个目标:
1.所有元素的全排列:ab的全排列是ab,ba(顺序相关);
2.所有元素的全组合:ab的全组合是a,b,ab(顺序无关);
3.求n个元素中选取m个元素的组合方式有哪些:abc中选2个元素的组合是ab,ac,bc;
4.求n个元素中选取m个元素的排列方式有哪些:abc中选2个元素的排列是ab,ba,ac,ca,bc,cb;
可以发现,求n个元素中选取m个元素的排列方式其实是在求出n个元素中选取m个元素的组合方式后,对每个组合组成的元素集(数组)做全排列,所以它是一个拼装函数,未列出示例,其他三个目标,看代码:
publicfinalclassPermutationCombinationHolder{ /**数组元素的全组合*/ staticvoidcombination(char[]chars){ char[]subchars=newchar[chars.length];//存储子组合数据的数组 //全组合问题就是所有元素(记为n)中选1个元素的组合,加上选2个元素的组合...加上选n个元素的组合的和 for(inti=0;i=m;--i){//从后往前依次选定一个 subchars[m-1]=chars[i-1];//选定一个后 combination(chars,i-1,m-1,subchars,subn);//从前i-1个里面选取m-1个进行递归 } } } /**数组元素的全排列*/ staticvoidpermutation(char[]chars){ permutation(chars,0,chars.length-1); } /**数组中从索引begin到索引end之间的子数组参与到全排列*/ staticvoidpermutation(char[]chars,intbegin,intend){ if(begin==end){//只剩最后一个字符时为出口 for(inti=0;i 以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。