字符串全排列问题

这几天一直在思考一个问题，一个字符串的排列方式有多少种？正好有阿里巴巴校园招聘的一道题目：

问“alibaba”这个字符串的排列方式有多少种？

看到这个问题，排列这个字眼，是不是有点眼熟，是啊！高二时候学习的排列组合问题，概率里面的。这算算都快10年过去了。

这里我们利用排列组合的问题解决这个问题。

看了下这个字符串，一共有7个字符，字符'a'出现了三次，字符'b'出现了2次，剩下了'l'与‘i’。

选择7个空位，这里由于相同的字符在每个空位置出现都是一样的，所以先安排重复的字符。

先考虑'a'，一共有C73（ps就是组合里的C）种方法，然后是出现两次的'b'；

这时候7个空位中已经有三个位置被选了，只剩下4个了，从这四个里面选择两个位置给‘b’，一共有C42种方法；

然后，7个空位剩下了2个了，个两个不同字符，有A22种排列方式。

所以总的字符串排列方式有C73*C42*A22=420种。

以上是利用了概率的方式来解答这个问题，怎么通过编程的方式实现呢？怎么设计算法呢？

还是查看一个简单的字符串吧，比如“xyz”。这个字符串一共有xyz，xzy，yxz，yzx，zxy，zyx。一共六种排列方法。

仔细观察这六种序列，是分别将x，y，z换到字符串的首位，然后对剩下的字符串进行排列。

这里为了更好地说明，我对新的字符串“xyza”这个排列逐层解析。

                                               第一层                      第二层              第三层      

第一行                                   x   yza                      x   y  za            x   y  z  a

                                                                                                           x  y  a   z

                                                                                x   z  ya            x   z a   y

                                                                                                           x   z  y   a

                                                                                 x   a   yz           x   a  y   z                                                                                                

                                                                                                          x   a  z   y

第二行                                  y   xza                      y  x  za               y  x z    a

                                                                                                           y   x a   z 

                                                                               y   z  xa              y   z  x   a

                                                                                                            y   z a    x 

                                                                                 y   a  xz             y   a  x   z 

                                                                                                             y   a  z   x 

第三行                                   z   yxa                      z  y  xa                 z  y  x    a

                                                                                                              z  y a    z

                                                                                z  x  ya                  z  x  y    a

                                                                                                              z  x  a    y

                                                                               z  a  xy                   z  a  x    y 

                                                                                                              z  a y    x   

第四行                                   a   yzx                      a y  zx                a   y  z   x

                                                                                                             a   y  x   z

                                                                               a  z  yx                 a  z  y    x

                                                                                                             a  z  x    y

                                                                                a  x  yz                a  x  y    z

                                                                                                             a  x   z   y   

这里可以明显地看出这是个递归运算，第一层是将字符串后面所有的字符分别进行置换，第二层与第一层执行的方式相似，这次只关注子串，然后第三层也是类似，终止条件子串已经到达字符串末尾。

然后按照这个思路我们有下面的代码：