题目来源 《剑指offer》

01 题目描述

给一个字符串如 "abc",请输出它的全排列。如 "abc"的全排列。abc, acb,bac,bca,cab,cba。

02 题解

大家在中学的时候是不是都学过排列组合，但是可能大部分都忘了，只记得公式了。今天帮大家回忆一下。

1.一个字符 "a"它的排列只有一种 "a"

2.两个字符的 "ab"它的排列有两种 ab，将b与首位a交换后的结果 ba。

3.三个字符的 "abc" 它的排列如何计算。

对于两个字符的，我们知道只有两种结果。那么对于三种字符的，我们可以先求两字符的再组合成三字符的。如abc

首先 a[bc] ，排列bc。得到结果，abc，acb。

然后将abc，中b与首位的a交换，即 b[ac]，固定b，排列ac。得结果bac，bca。

将abc中c与首位的a交换即 c[ba]，固定c。排列ba的结果cba，cab。

所以最终得到 abc，acb，bac，bca，cba，cab六种结果。

结合中学排列种数的算法，3个字符*（每个字符为首位时对应的剩余2个字符的两种排列）*1中字符的一种排列=6

4.针对四个字符的，abcd，如何来找它的排列呢。

（1）a[bcd]

（2）b与首位a交换 b[acd]

（3）c与首位a交换 c[bad]

（4）d与首位a交换 d[bca]

剩余的三个字符，就回到了三种字符的排列

03 代码和总结

整个过程就是交换字符

两个字符是ab，分别将a，b交换至首位。得ab，ba，

三个字符时 abc 分别将a，b，c交换至首位。

再进入到两个字符的交换，最后一个字符时输出。

以此类推。

public static void permutation(char [] chars) { if (chars == null || chars.length == 0) { return; } permutation(chars, 0);// 从数组中第零位开始。}// 真正的排列函数public static void permutation(char [] chars, int beginIndex) { int length = chars.length; if (beginIndex == length) { System.out.println(Arrays.toString(chars)); } for (int i = beginIndex; i < length; i ++) { char tmp = chars[beginIndex];// 交换，递归到的层数的首位与后面的值 chars[beginIndex] = chars[i]; chars[i] = tmp; permutation(chars, beginIndex + 1); tmp = chars[beginIndex];// 归位交换，i++进行下一个数与首位交换。 chars[beginIndex] = chars[i]; chars[i] = tmp; }}// 测试用例public static void main(String[] args) { String str = "abc"; permutation(str.toCharArray()); String str1 = "abcd"; permutation(str1.toCharArray()); String str2 = ""; permutation(str2.toCharArray());}