额 我基础测试碰到的就是这道题。。楼主可以参考一下。。- package com.study.two;
- import java.util.ArrayList;
- import java.util.List;
- /**
- *
- * 编程列出一个字符串的全字符组合情况,原始字符串中没有重复字符
- 例如:
- 原始字符串是"abc",打印得到下列所有组合情况
- "a" "b" "c"
- "ab" "bc" "ca" "ba" "cb" "ac"
- "abc" "acb" "bac" "bca" "cab" "cba"
- *
- */
- /**
- * 思路:1.先把字符串转化为数组
- * 2.先是进行数组的排列组合
- * 例如输入abc,那么输出的组合应该是a,b,c,ab,ac,bc,abc。
- * 3. 然后再是数组的全排列
- * 如输入的是abc,则输出的是abc,acb,bac,bca,cab,cba。
- * 4. 最后结合起来可以得出题目结果
- *
- *
- */
- public class Test5 {
- //数组的排列组合,例如输入abc,那么输出的组合应该是a,b,c,ab,ac,bc,abc。
- //算法:假设我们想在长度为n得字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符,针对第一个字符有两种选择。
- //一种是把该字符放进集合里,然后对剩下的n-1个字符中挑出m-1个字符。
- //另一种是不把该字符放进集合里,然后是对剩下的n-1个字符中挑出m个字符。
- //combination(char chs[])方法和combine(char []cs,int begin,int number,List <Character> list)
- //方法是上面的排列组合的实现。最后再在排列组合的基础上加上(全排列组合)。则可以实现题目的要求。
- public static void combiantion(char chs[]){
- //如果数组为空则返回空
- if(chs==null||chs.length==0){
- return ;
- }
- //定义集合接收排列组合结果
- List <Character> list=new ArrayList<Character>();
- //字符串的1个,2个,3个....字符总长长度,字符的排列组合
- for(int i=1;i<=chs.length;i++){
- //从0位置开始扫描
- combine(chs,0,i,list);
- }
- }
- //从字符数组中第begin个字符开始挑选number个字符加入list中
- public static void combine(char []cs,int begin,int number,List <Character> list){
- //当挑选的字符数扫描到0时,将集合中的数据取出来进行全排列组合
- if(number==0){
- char cc[]=new char[list.size()];
- for(int j=0;j<list.size();j++){
- cc[j]=list.get(j);
- }
- //对排列组合后的字符进行全排列
- permutation(cc, 0);
- return ;
- }
- //当begin位循环到字符最后时,不再向下扫描,否则抛出数组溢出异常
- if(begin==cs.length){
- return;
- }
- //第一种情况,扫描到的第一个字符,加入的集合中去
- list.add(cs[begin]);
- //从剩下的字符中,扫描number-1个字符到集合中区
- combine(cs,begin+1,number-1,list);
- //第二种情况,扫描到的第一个字符不加入集合里头去,移除添加到数组中的字符
- list.remove((Character)cs[begin]);
- //从子符数组下一位挑选number个字符放入list中
- combine(cs,begin+1,number,list);
- }
- //数组的全排列组合
- //如输入的是abc,则输出的是abc,acb,bac,bca,cab,cba。
- //算法:如abcde 首先是首位是a的情况下,全排列剩下的。然后交换1-2位数字,即首位是b的情况,全排列的。以此类推。
- //用permutation自身对剩下的数组进行全排列,在permutation函数内,
- //只要判断出来数组中只有一个元素时,无需再排列,直接打印数组即可。
- //因为依次对1-2位,2-3位,1-4位进行交换,所以每次交换后,需要再次交换,使数组归位。
- public static void permutation(char[]ss,int i){
- //为了交换数据,定义中间变量
- char temp;
- 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++){
- //交换前缀,使之产生下一个前缀
- temp=ss[j];
- ss[j]=ss[i];
- ss[i]=temp;
- //对i+1位之后剩下的元素进行全排列
- permutation(ss,i+1);
- //将前缀换回来,继续做上一个的前缀排列.
- temp=ss[j];
- ss[j]=ss[i];
- ss[i]=temp;
- }
- }
- }
- public static void main(String args[]){
- String str=new String("abcd");
- //字符串转换成数组
- char chss[]=str.toCharArray();
- combiantion(chss);
- }
-
- }
复制代码 |