从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m＝n时所有的排列情况叫全排列。以下的解法都以字符串的全排列为列。
逐步生成的解法：
这种解法的特点在于：从1个元素的全排列慢慢推出n个元素的全排列。一个元素的全排列推出两个元素的全排列，然后两个元素的全排列再推出三个元素的全排列。直到推出n个元素的全排列。
以数字1，2，3为例，可以采用树的结构表示全排列生成算法，以数字的全排列生成算法为例，从最小的数1开始，其全排列只有一种可能;加入数字2，数字2可以插入在1的后边或前边，有两个不同位置;再加入3，对于第二层中的每一种不同排列，都可以通过将3插入不同位置得到三种不同的排列数，共有6种排列数;一次类推可以得3个数的全排列。
迭代写法如下：
import java.util.*;
public class 全排列迭代写法 {
public static void main(String[] args){
String str = "abc";
System.out.println(perm(str));
}
private static Set<String> perm(String str) {
Set<String> resset = new HashSet();
resset.add(str.charAt(0)+ "");
for(int i=1; i<str.length(); i++){//每一次循环产生i个字母的所有全排列集合
Set<String> set = new HashSet();
for(String s:resset){
char c = str.charAt(i);
//必须将加在最前面和加在最后面从循环中单独拿出来
//否则会影响循环的次数
set.add(c + s);//添加在最前面
set.add(s+c);//添加在最后面
for(int j=1; j<s.length(); j++){//在中间插入新字符
String t = s.substring(0,j) + c + s.substring(j);
set.add(t);
}
}
resset = set;//新的一层集合覆盖原来的集合
}
return resset;
}
}
递归写法如下：
import java.util.*;
public class 全排列递归写法 {
public static void main(String[] args){
String str = "abc";
System.out.println(perm(str,str.length(), str.length()-1));
}
private static Set<String> perm(String str, int n, int cur) {
Set<String> newset = new HashSet();
if(cur==0){
newset.add(str.charAt(0)+"");
return newset;
}
Set<String> set = perm(str, n-1, cur-1);
for(String s:set){
char c = str.charAt(cur);
newset.add(c + s);//添加在最前面
newset.add(s+c);//添加在最后面
for(int j=1; j<s.length(); j++){//在中间插入新字符
String t = s.substring(0,j) + c + s.substring(j);
newset.add(t);
}
}
return newset;
}
}
回溯解法：
回溯解法的特点在于多支路的递归，以字母举例：先找出A开头的排列，然后再找出B开头的排列，最后找出C开头的排列。它的生成树的生成过程是先纵后横。越往下支路会不断减少，到一条支路走到底的时候就得到了一种全排列；然后进行回溯。到A开头这个大支路走完后需要回到根节点开始走B开头的支路。
代码如下：
import java.util.*;
public class 全排列回溯写法 {
public static void main(String[] args){
String str = "abc";
char[] a = str.toCharArray();
ArrayList<String> res = new ArrayList();
perm(a, 0, res);
System.out.println(res);
}
/**
* @param a
* @param n
* @param res
* 将数组下标k以及之后的元素全排列的结果添加进res中
*/
private static void perm(char[] a, int k, ArrayList res) {
if(k==a.length){//得到了一种全排列，生成树的其中一条支路走到底了
String str = new String(a);
res.add(str);
}
//从k位开始的每一个字符都尝试放在新排列的k这个位置
for(int i=k; i<a.length; i++){
swap(a, k, i);//将后面的字母换到k位
perm(a, k+1, res);//将k-1后的元素进行全排列
swap(a, k, i);//回溯
}
}
private static void swap(char[] a, int k, int i) {
char temp = a[k];
a[k] = a[i];
a[i] = temp;
}
}
这个代码如果需要处理有重复的情况把ArrayList改为Set就行了。