1.题目描述：
给定字符串“abc”，求abc的全排列。
思考：我们最容易想到的办法就是枚举法：暴力求解。大致思路如下
/**
* 暴力求解
*/
public static void permutation(){
String string="abc";
for(int i=0;i<string.length();i++){
for(int j=0;j<string.length();j++){
for(int k=0;k<string.length();k++){
if(i!=j&&i!=k&&k!=j){
System.out.println(string.charAt(i)+""+string.charAt(j)+""+string.charAt(k));
}
}
}
}
}
输出的结果是：
abc
acb
bac
bca
cab
cba
上面的程序有没有问题呢？1.首先，时间复杂度很高，与字符串的长度n的关系式o(n^n)。2.其次：当字符串长度不确定时，上面的代码几乎没办法做。
题目二：
给定无重复的字符集,求这些字符的全排列。如：{a,b,c}，那么其全排列则为：
abc
acb
bac
bca
cab
cba
思路：我们设计如下递归算法：
/**
* 求字符串str的全排列
* @param str
* @param str2 辅助字符串
* @return 全排列的结果
*/
public static List<String> permutation(String str,String str2){
List<String> result= new ArrayList<String>();
if(str.length()==0){
result.add(str2);
System.out.println(str2);
return result;
}
for(int i=0;i<str.length();i++){
StringBuffer temp=new StringBuffer(str);
//递归：逐步将str的第i个字符分给str2
List<String> list = permutation(temp.deleteCharAt(i).toString(),str.charAt(i)+str2);
result.addAll(list);
}
return result;
}
调用方式：
List<String> result= permutation("abcd", "");
此程序，我们计算的是，字符串str中的全排列。如果问题修改一下，我们该怎么修改程序呢？
题目三：
给定n个不同的字符，求其任意K（K<=n）个元素的全排列。例如，
输入：
abc
2
输出：
ba
ca
ab
cb
ac
bc
思考：我们只需要修改上述递归方法的边界条件即可。也就是当str2的长度为K的时候，将str2保存即可：
/**
* 求字符串str的长度为K的全排列
* @param str
* @param str2
* @param k
* @return
*/
public static List<String> permutation(String str,String str2,int k){
List<String> result= new ArrayList<String>();
if(str2.length()==k){
result.add(str2);
System.out.println(str2);
return result;
}
for(int i=0;i<str.length();i++){
StringBuffer temp=new StringBuffer(str);
//递归：逐步将str的第i个字符分给str2
List<String> list = permutation(temp.deleteCharAt(i).toString(),str.charAt(i)+str2,k);
result.addAll(list);
}
return result;
}
调用方式：
permutation("abc", "",2);
题目四：
字符串alibaba的所有不同的排列
思考：我们都知道，不同的排列数目为
也就是420中情况。根据题目2中的递归函数，我们知道，如果直接使用题目2的递归方法，得出的结果是6！中，其中有3!*2!是重复的。因此，我们就要考虑将List中重复的数据删除，此时，我们应该使用HashSet容器，它可以有效的避免元素重复的情况。
public static Set<String> permutation2(String str,String str2){
Set<String> result= new LinkedHashSet<String>();
if(str.length()==0){
result.add(str2);
return result;
}
for(int i=0;i<str.length();i++){
StringBuffer temp=new StringBuffer(str);
//递归：逐步将str的第i个字符分给str2
Set<String> set = permutation2(temp.deleteCharAt(i).toString(),str.charAt(i)+str2);
result.addAll(set);
}
return result;
}
调用：
Set<String> set = permutation2("alibaba", "");
System.out.println(set.size());
for(String str:set){
System.out.println(str);
}
以上问题，纯属个人的思考，不能保证权威性。