字符串的排列

题目描述

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

输入描述：输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

分析

以字符串abc为例。

1. 固定第一个字符a，然后剩下的字符为bc。
2. 将bc重复第一个步骤，即固定第一个字符b，剩下c。
3. 到最后一个字符时，即已经排完第一次序列，将序列abc放进结果数组$res[]。
4. 这时回到步骤2，被固定的字符b与它的下一个字符交换，即这次固定的是c，再到步骤3是acb，放进结果数组。（注：这里的目的就是将当前的固定字符与它后面的字符都互换一遍，达到组合的效果。）
5. 最后，将步骤1的a与它后面的字符b、c都互换位置，重复以上步骤。

如果遇上重复字符，例如abb，则需要一个额外数组来记录当前位置已经换过的字符。比如在固定第二个字符b的时候，记录它，当它与后面的字符互换时，发现与第三个字符b相等，则跳过这个字符。

代码

<?php

namespace app\index\controller;

class Test
{
    /**
     * 排列函数
     * @param string $str 字符串
     */
    public function Permutation($str)
    {
        if (empty($str)) return [];

        $arr   = str_split($str);  // 字符串转数组
        $res   = [];               // 存放最终结果的数组
        $print = '';               // 存放每次的排序

        $this->dfs(0, $arr, $res, $print);  // 调用函数
        print_r($res);
    }


    /**
     * @param $index  表示正在固定位置的字符下标
     * @param $arr    字符串转换而来的数组
     * @param $res    存放全部排序的数组
     * @param $print  存放每次排序的字符串
     */
    public function dfs($index, $arr, &$res, $print)
    {
        $length = count($arr);

        // 如果遍历到最后一个字符，则将排完序的字符串放进 $res[]
        if ($index == $length - 1) {
            $res[] = $print . $arr[$index];
            return;
        }

        $used = [];  // 这个是存放已固定过的字符，避免出现重复字符而导致重复排序

        for ($i = $index; $i < $length; $i++) {
            if (in_array($arr[$i], $used)) continue; // 如果当前字符已固定过，则剪枝
            $used[] = $arr[$i];                      // 将字符添加进已固定字符的数组

            $this->swap($arr[$index], $arr[$i]);  // 交换，i位置的字符与index位置的字符互换
            $this->dfs($index + 1, $arr, $res, $print . $arr[$index]);  // 递归，固定下一个位置的字符
            $this->swap($arr[$index], $arr[$i]);  // 恢复交换
        }
    }


    /**
     * 值互换
     */
    public function swap(&$left, &$right)
    {
        $tmp   = $left;
        $left  = $right;
        $right = $tmp;
    }

}

测试

/**
* 输入字符串
*/
public function test()
{
    $str = 'abc';
    $this->Permutation($str);
}