对一个字符串全排列

字符串全排列"/>

对一个字符串全排列

所谓全排列就是：

从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列

假设给出一个字符串,那么对进行全排列结果如图：

这明显是一棵树，可以用递归来实现，但是我们采用非递归的方式，更容易理解。

直接贴代码，然后来分析思路：

public static ArrayList<String> getPermutation(String A){int n=A.length();ArrayList<String> res=new ArrayList<>();res.add(A.charAt(0)+"");for (int i = 1; i <n ; i++) {ArrayList<String> res_new =new ArrayList<>();char c=A.charAt(i);for (String str:res){String newStr=c+str;//在前面插入字符res_new.add(newStr);newStr=str+c;//在后面插入字符res_new.add(newStr);for (int j = 1; j < str.length(); j++) {//在中间插入字符newStr=str.substring(0,j)+c+str.substring(j);res_new.add(newStr);}res=res_new;//把每次处理好的结果给res}}return res;}

首先选定一个字符作为起始字符，用ArrayList集合存储结果，然后从第二个字符开始遍历字符串，第二个for循环是用来给结果字符串在前后插入新的字符的，第三个for循环是在中间插入字符。

举个栗子：例如给定字符串abc

运行过程为

第一次遍历:res=[a]

res_new=[ab]

res_new=[ab,ba]

res=[ab,ba]

第二次遍历结果

res=[ab,ba]

res_new=[abc,cab,cba,bac]

res_new=[abc,cab,cba,bac,acb,bca]

res=[abc,cab,cba,bac,acb,bca]

思考:如果给的字符串有重复字符，那结果必定会出现重复的记录，我们想要不重复的记录怎么办?

我们可以使用Hashset集合进行去重：

HashSet<String> cos=new HashSet();for (String str: res) {cos.add(str);}