我们在笔试面试过程中经常会遇到关于排列与组合的问题,其实这些可以通过递归简单的实现,看下面两个例子:
(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(ss==null||i<0 ||i>ss.length){
return;
}
if(i==ss.length){
System.out.println(new String(ss));
}else{
for(int j=i;j<ss.length;j++){
char temp=ss[j];//交换前缀,使之产生下一个前缀
ss[j]=ss[i];
ss[i]=temp;
permutation(ss,i+1);
temp=ss[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(chs==null||chs.length==0){
return ;
}
List<Character> list=new ArrayList();
for(int i=1;i<=chs.length;i++){
combine(chs,0,i,list);
}
}
//从字符数组中第begin个字符开始挑选number个字符加入list中
public static void combine(char []cs,int begin,int number,List<Character> list){
if(number==0){
System.out.println(list.toString());
return ;
}
if(begin==cs.length){
return;
}
list.add(cs[begin]);
combine(cs,begin+1,number-1,list);
list.remove((Character)cs[begin]);
combine(cs,begin+1,number,list);
}
public static void main(String args[]){
char chs[]={'a','b','c'};
combiantion(chs);
}
}
参考:http://zhedahht.blog.163.com/blog/static/2541117420114172812217/
http://zhedahht.blog.163.com/blog/static/254111742007499363479/
分享到:
相关推荐
排列与组合的Java递归实现.doc
本资源附带文档解释了排列组合算法的实现和原理。其中排列算法是基于递归实现的,组合算法是基于高效的位移法实现的。代码是使用Java版实现的。
java m取n 重复 不重复 排列组合 for循环嵌套递归
排列组合算法实现,支持模板类。支持重复数的排列。算法采用递归方法,简单易懂。
Java排列组合_组合算法,利用list及set的无序性, 通过递归实现,不同于以往的排列组合 自娱自乐
此外,文档还提供了各种排列组合算法的详细代码示例和实现细节,包括递归和迭代方法。文档还涵盖了高级主题,如如何计算有重复元素的排列组合数量,以及如何优化这些算法的性能。 无论您是Java编程的初学者还是有...
主要为大家详细介绍了Java递归实现字符串全排列与全组合,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
只需改变里面一处数据,就可以根据自己需要,执行输出n个数中取m个数的所有组合。
我得意之作,采用递归实现。排列组合。希望对大家有用。@TTgdz
今天 写了一个java小程序 是将a,b,c,d,e,f,g这7个字母的全排列打印出来,排除a,d相邻的情况 算然很简单 但是我用递归调用的方式写的 算法还是很不错的 建议新手们学习 看不懂或者有更好的想法的的请留言^_-
2016-09-24_213732.wmv ...22_排列组合(1).flv 23_排列组合(2).flv 24_概率(1).flv 25_概率(2).flv 26_队列和栈(2).flv 27_大数据(1).flv 28_大数据(2).flv 29_动态规划(1).flv 30_动态规划(2).flv
为了获得字符串的排列,本实践提出了使用递归方法的解决方案。 置换生成器: 基本条件发生在字符串中只有一个字符时。 如果字符串有 n 个字符,(循环 'i' 从 0 到 n-1)该方法将第 'i' 个字符作为第一个字符,并...
常见数据结构与算法小结(Java语言描述) 这是一个数据结构和算法笔记本,书写 并 整理一些常见的数据结构和其对应的相关操作。这其中每一个类文件都是一个可以单独运行查看结果的main方法类,相关的关键描述和想说...
1.9.3排列组合、概率论应用、应用统计 34 1.9.4线性规划 37 专题二:程序语言部分 39 1、程序语言知识 39 1.1 程序语言: 39 1.2 汇编语言: 42 1.3 解释程序: 42 1.4 编译程序: 43 2.重点与难点 45 2.1文法及...
通过此课题,熟练掌握文件、数组、指针的各种操作,以及一些递归算法思想的应用。 (1)统计显示英文文档中所有出现的字母及出现次数; (2)计算字母出现次数百分比及发布图(或表); (3)对词频统计结果进行词频升序、...
java lru leetcode Problem Tag Level 用哈希表记住遍历过的元素、O(1)查找 Easy 链表、遍历完两串中较长的那个、取默认值 Medium dp、中心点扩展法 Medium 格式化 Medium 字符串处理、判断int溢出 Medium 首尾双...
排列组合,概率论应用,应用统计(数据的统计分析) 编码基础 命题逻辑、谓词逻辑、形式逻辑的基础知识 运筹基本方法 2. 计算机系统知识 2.1计算机硬件基础知识 2.1.1计算机系统的组成、体系结构分类及...
如何递归定义括号字符串的有效性并找出一种轻松分治的方法? 022 如何使组合支架始终平衡? 050 幂到一个非常大的指数。 102 (Java) 泛型不是协变 659 Python 集合和枚举的使用。 子序列和子串的区别。 660去掉9是...
java lru leetcode 力码练习 基本:快速排序 解决方案 日期 未解决 基础:堆排序 解决方案 日期 未解决 4. 两个有序数组的中位数 解决方案 日期 原来的 9/17 提升 LintCode 5. 第 K 个最大元素 解决方案 日期 划分 8...
一、数独说明:数独由九行,九列组成,又分为顺序排列的九宫。每行、每列及每宫都包含九个格,九个格中填放1到9的不重复的数字。 二、自动计算原理(三步法): 1、基础法:找出空格中唯一可填的数字。方法是,先...