这是一个面试题。
给定一个字符串，输出这个字符串的全排列。比如给定了字符串abc，那么输出结果就是
abc acb bac bca cab cba
如果用Python来解决这个问题的话，那真的是非常非常简单的了，因为Python有个itertools工具包，这个包下有个工具类叫permutations。
几行代码就可以实现功能：
(perm.py) download 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#!/usr/bin/env python
# coding:utf8
from itertools import permutations
def main ():
result = permutations ( 'abc' )
for v in result :
print v
if __name__ == "__main__" :
main ()
当然我们不能这么赖皮地使用Python的内置库来解决这个问题，更重要的是，我们需要了解全排列的算法。
所谓全排列，就是打印出字符串中所有字符的所有排列。例如输入字符串abc，则打印出 a、b、c 所能排列出来的所有字符串 abc、acb、bac、bca、cab 和 cba 。
一般最先想到的方法是暴力循环法，即对于每一位，遍历集合中可能的元素，如果在这一位之前出现过了该元素，跳过该元素。例如对于abc，第一位可以是 a 或 b 或 c 。当第一位为 a 时，第二位再遍历集合，发现 a 不行，因为前面已经出现 a 了，而 b 和 c 可以。当第二位为 b 时 ， 再遍历集合，发现 a 和 b 都不行，c 可以。可以用递归或循环来实现，但是复杂度为 O(nn ) 。有没有更优雅的解法呢。
首先考虑bac和cba这二个字符串是如何得出的。显然这二个都是abc中的 a 与后面两字符交换得到的。然后可以将abc的第二个字符和第三个字符交换得到acb。同理可以根据bac和cba来得bca和cab。
因此可以知道，全排列就是从第一个数字起每个数分别与它后面的数字交换，也可以得出这种解法每次得到的结果都是正确结果，所以复杂度为 O(n!)。
最后我写了一个PHP版本的实现：
(perm.php) download 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
<? php
/**
* Created by PhpStorm.
* User: caiknife
* Date: 2018/11/17
* Time: 15:09
*/
namespace App\Cron ;
class StringPlace
{
public function main ()
{
$this -> stringPlace ( 3 );
}
public function stringPlace ( $stringSize = 10 )
{
$tmpString = [];
for ( $i = 0 ; $i < $stringSize ; $i ++ ) {
$tmpString [] = chr ( rand ( 97 , 122 ));
}
echo "Origin string is " . implode ( '' , $tmpString ) . PHP_EOL ;
$this -> perm ( $tmpString , 0 , sizeof ( $tmpString ) - 1 );
}
public function perm ( & $arr , $k , $m )
{
if ( $k == $m ) {
echo implode ( '' , $arr ) . PHP_EOL ;
} else {
for ( $i = $k ; $i <= $m ; $i ++ ) {
$this -> _swap ( $arr [ $k ], $arr [ $i ]);
$this -> perm ( $arr , $k + 1 , $m );
$this -> _swap ( $arr [ $k ], $arr [ $i ]);
}
}
}
protected function _swap ( & $a , & $b )
{
list ( $b , $a ) = [ $a , $b ];
}
}
全排列就是这样，代码看起来还是有点点难懂，需要深入了解才能融会贯通。