但行好事,莫问前程

挖了太多坑,一点点填回来

趣味题:求字符串的全排列

实战, 数据结构, 算法, 编程

这是一个面试题。

给定一个字符串,输出这个字符串的全排列。比如给定了字符串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];
    }
}

全排列就是这样,代码看起来还是有点点难懂,需要深入了解才能融会贯通。