全排列-迭代法求全部排列（去重）

问题

描述

求指定字符串的全部排列（去重）

思路

从第一个字符起，每个字符分别与它后面不相等的字符交换位置！

Code

public class arrange_Iteration {
	static long sum;
	static boolean same(String s,int b,int e) {
		for(int i=b;i<e;i++) {
			if(s.charAt(i)==s.charAt(e))
				return false;
		}
		return true;
	}
	static void fun(ArrayList a,int t,String s) {
		if(t<s.length()-1) {
			int i,j,n;
			n=s.length();
			char x,y;
			String z;
			z=s;
			for(i=t;i<n-1;i++) {
				s=z;
				for(j=i+1;j<n;j++) {
					if(same(s,i,j)) {
						x=s.charAt(i);
						y=s.charAt(j);
						s=s.substring(0,i)+y+s.substring(i+1,j)+x+s.substring(j+1,n);
						a.add(s);
						sum++;
						fun(a,i+1,s);
					}else {
						continue;
					}	
				}
			}

		}
	}
	public static void main(String[] args) {
		Scanner as=new Scanner(System.in);
		String s;
		int i;
		while(as.hasNext()) {
			s=as.nextLine();
			ArrayList a=new ArrayList<>();
			sum=1;
			a.add(s);
			fun(a,0,s);
			System.out.println(sum+"个,");
			for(i=0;i<a.size();i++)
				System.out.println(a.get(i));
		}
	}

}

解析

• same(String s,int b,int e)函数判断字符串中从第b个位置起到第e个位置之前，是否有与第e个位置相同的字符串；有返回false，没有返回true；实现去重效果！
• fun(ArrayList a,int t,String s)函数递归函数，将字符串s排列并记录数量与字符串；
• 运用Java中的动态数组来存储所有的字符串排列，最后输出！