Java之字符串数组元素的排列与组合（递归实现）

今天药忘吃喽~ 2022-05-14 07:16 282阅读 0赞

### 1.字符数组元素的组合 ###

字符数组元素的组合通常是要求输入一个字符串，然后输出得到字符串中字符的所有组合。例如输入字符串“abc”，输出为“a”，“b”，“c”，“ab”，“ac”，“bc”，“abc”这七种组合方式。求解思路：假设要在长度为len的字符串中求num个字符的组合，可以先从头扫描字符串的第一个字符，对于第一个字符可以有两种处理方式：一是把这个字符放到组合中去，接下来还需要在剩下的n-1个字符中选取m-1个字符；二是不把这个字符放到组合中去，接下来需要在剩下的n-1个字符中选择m个字符。

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    /*该程序先根据输入的两个字符串找出其中相同的字符，然后根据指定的组合长度求出各种可能的组合
    *
    */
    public class CharArrayCombine {
    	public static void main(String[] args) {
    		String user="AdHRgwxy";
    		String mothers="aDRmgqh";
    		password(user,mothers,3);
    	}
    	
    	public static void password(String userName,String motherName,int pwdlen) {
    		char[] me=userName.toLowerCase().toCharArray();
    		char[] mother=motherName.toLowerCase().toCharArray();
    		char[] array=new char[me.length];
    		int index=0;
    		for(int i=0;i<me.length;i++) {
    			if(find(mother,me[i])==true&&find(array,me[i])==false) {
    				array[index]=me[i];
    				index++;
    			}
    		}
    		for(int i=0;i<index-1;i++) {
    			for(int j=0;j<index-1-i;j++){
    				if(array[j]>array[j+1]) {
    					char temp=array[j];
    					array[j]=array[j+1];
    					array[j+1]=temp;
    				}
    			}
    		}
    		List<Character> list=new ArrayList<Character>();
    		combine(array,0,index-1,pwdlen,list);
    	}
    	/*字符数组的组合
    	 * 
    	 */
    	public static void combine(char[] array,int start,int end,int number,List<Character> list) {
    		if(number==0) {
    			String out="";
    			for(Character c:list) {
    				out=out+c.toString();
    			}
    			System.out.print(out+" ");
    			return;
    		}
    		if(start>end) {
    			return;
    		}
    		list.add(array[start]);
    		combine(array,start+1,end,number-1,list);
    		list.remove((Character)array[start]);
    		combine(array,start+1,end,number,list);
    	}
    	
    	/*查找字符数组中是否有指定的字符
    	 * 有则返回true，否则返回false
    	 */
    	public static boolean find(char[] array,char c) {
    		boolean flag=false;  //默认字符数组没有待查找的字符
    		for(int i=0;i<array.length;i++) {
    			if(array[i]==c) {
    				flag=true;
    				break;
    			}
    		}
    		return flag;
    	}
    }

输出结果：adg adh adr agh agr ahr dgh dgr dhr ghr

import java.util.ArrayList;
    import java.util.List;
    
    public class CharCombine{
    	public static void main(String args[]){  
            char[] array={'a','b','c'};  
            combiantion(array);  
        }  
        public static void combiantion(char[] array){  
            if(array==null||array.length==0){  
                return ;  
            }  
            List<Character> list=new ArrayList();  
            for(int i=1;i<=array.length;i++){  
                combine(array,0,i,list);  
            } 
        }  
        //从字符数组中第begin个字符开始挑选number个字符加入list中  
        public static void combine(char[] array,int begin,int number,List<Character> list){  
            if(number==0){
            	String out="";
    			for(Character c:list) {
    				out=out+c.toString();
    			}
    			System.out.print(out+" ");
    			return; 
            }  
            if(begin==array.length){  
                return;  
            }  
            list.add(array[begin]);  
            combine(array,begin+1,number-1,list);  
            list.remove((Character)array[begin]);  
            combine(array,begin+1,number,list);  
        }  
    }

输出结果：a b c ab ac bc abc

--------------------

### 2.字符数组元素的排列 ###

字符数组元素的排列通常是要求输入一个字符串，然后输出字符串中字符的所有排列。例如输入字符串“abc”，输出的排列组合为“abc”、“acb”、“bac”、“bca”、“cab”、“cba”这六种排列。求解思路：固定第一个字符a，求后面两个字符bc的排列。当b和c两个字符的排列求完后，我们把第一个字符a和后面的b交换，得到bac;接着我们固定第一个字符b，求后面两个字符ac的排列。依次这样进行下去，需要注意的是，前面已经把原先的第一个字符a和后面的b做了交换，为了保证这次c仍然是和原先处在第一位置的a交换，我们在拿c和第一个字符交换之前，先要把b和a交换回来。在交换b和a之后，再拿c和处在第一位置的a进行交换，得到cba。

public class CharArrangement{
    
    	public static void main(String[] args) {
    		String str="abc";
    		char[] array=str.toCharArray();
            arrangement(array, 0);		
    		// TODO Auto-generated method stub
    	}
    	public static void arrangement(char[] array,int i) {
    		if(array==null||i<0||i>array.length){
    			return;
    		}else if(i==array.length) {
    			String out="";
    			for(int j=0;j<array.length;j++) {
    				out=out+array[j];
    			}
    			System.out.print(out+" ");
    		}else {
    			char temp;
    			for(int j=i;j<array.length;j++){
                    temp=array[j];
                    array[j]=array[i];
                    array[i]=temp;
                    arrangement(array, i+1);
                    temp=array[j];
                    array[j]=array[i];
                    array[i]=temp;
                }
    		}
    	}
    }

输出结果：abc acb bac bca cba cab

本文参考了：[https://www.cnblogs.com/565261641-fzh/p/5398454.html][https_www.cnblogs.com_565261641-fzh_p_5398454.html]

[https_www.cnblogs.com_565261641-fzh_p_5398454.html]: https://www.cnblogs.com/565261641-fzh/p/5398454.html