《剑指Offer》-38.字符串的排列

题干

输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则打印出由a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。

解题思路

求整个字符串的排列，可以看出两步，第一步求所有可能出现在第一个位置的字符，即把第一个字符和后面所有的字符交换。第二步固定第一个字符，求后面所有字符的排列，而后面所有字符的排列又可以递归上面的两步完成。

代码实现

<?php
function permutation($str)
{
    if (empty($str)) {
        return;
    }

    doPermutation($str, 0);

}

function doPermutation($str, $pos)
{
    if ($pos == mb_strlen($str) - 1) {
        echo $str.PHP_EOL;
    } else {
        for ($i = $pos; $i < mb_strlen($str); $i++) {
            $tmp = $str[$pos];
            $str[$pos] = $str[$i];
            $str[$i] = $tmp;

            doPermutation($str, $pos + 1);

            $tmp = $str[$pos];
            $str[$pos] = $str[$i];
            $str[$i] = $tmp;
        }
    }
}

permutation('abc');