来源:
经典的全排列问题
描述
给定一个字符串,输出他的全排列。
样例
代码语言：javascript复制给定"ABC"
输出:
ABC
ACB
BCA
BAC
CAB
CBA解题思路:
这道题是数学中的全排列问题,输出结果的个数为n!.
那么怎么获得具体的所有排列呢?
对于ABC来说,
排列的第一位有三种可能:ABC,当第一位确定之后,第二位有两种可能,第三位只有一种可能.
首先确定第一位,可能是3种,分别计算.
代码语言：javascript复制A---的第二位可能是B,C,全排列分别为:
ABC
ACB
B---的第二位可能是AC,全排列分别为:
BAC
BCA
C---的第二位可能是AB,全排列分别为:
CBA
CAB可以看出,ABC的全排列为:
(A (BC的全排列)) (B (AC的全排列)) (C (AB的全排列)).
可以使用递归来实现.
实现代码
代码语言：javascript复制 /**
* 全排列递归实现
*/
private List<String> quanpailie(char[] cs, int current) {
//结果
List<String> result = new LinkedList<>();
//当前指向数组最后一位时,将数组(全排列的一种)输出到结果集里
if (current == cs.length - 1) {
result.add(Arrays.toString(cs));
} else {
//循环改变数组的第一个位置的值,并求剩下的其他字符的全排列,并装入结果集.
for (int i = current; i < cs.length; i ) {
//交换当前字符与下一字符
swap(cs, current, i);
//这一块难理解,相当于,在A确定放在第一位的时候,求BC的全排列,并且加上A,形成ABC,ACB放入结果集.
result.addAll(quanpailie(cs, current 1));
//交换回来,方便下一次交换.
swap(cs, current, i);
}
}
return result;
}
/**
* 交换数组第b,e位置上的值
*/
private void swap(char[] cs, int b, int e) {
char tmp = cs[b];
cs[b] = cs[e];
cs[e] = tmp;
}完。
ChangeLog
2018-12-11 完成
以上皆为个人所思所得，如有错误欢迎评论区指正。
欢迎转载，烦请署名并保留原文链接。
联系邮箱：huyanshi2580@gmail.com
