计算字符串下一个排列.md

计算字符串下一个排列

首先了解next_permutation算法过程，先分析“下一个排列”的性质。

• 假定现有字符串(A)x(B)，它的下一个排列是：(A)y(B’)，其中A、B和B’是“字符串”(可能为空），x和y是“字符”，前缀相同，都是A，且一定有y > x。
• 那么，为使下一个排列字典顺序尽可能小，必有：
  • A尽可能长
  • y尽可能小
  • B’里的字符按由小到大递增排列

现在的问题是：找到x和y。怎么找到呢？咱们来看一个例子。

比如说，现在我们要找21543的下一个排列，我们可以从左至右逐个扫描每个数，看哪个能增大（至于如何判定能增大，是根据如果一个数右面有比它大的数存在，那么这个数就能增大），我们可以看到最后一个能增大的数是：x = 1。

而1应该增大到多少？1能增大到它右面比它大的那一系列数中最小的那个数，即：y = 3，故此时21543的下一个排列应该变为23xxx，显然 xxx(对应之前的B’）应由小到大排，于是我们最终找到比“21543”大，但字典顺序尽量小的23145，找到的23145刚好比21543大。

由这个例子可以得出next_permutation算法流程为：

next_permutation算法

• 定义
  • 升序：相邻两个位置ai < ai+1，ai 称作该升序的首位
• 步骤（二找、一交换、一翻转）
  • 找到排列中最后（最右）一个升序的首位位置i，x = ai
  • 找到排列中第i位右边最后一个比ai 大的位置j，y = aj
  • 交换x，y
  • 把第(i+ 1)位到最后的部分翻转

还是拿上面的21543举例，那么，应用next_permutation算法的过程如下：

• x = 1；
• y = 3
• 1和3交换
  • 得23541
• 翻转541
  • 得23145

23145即为所求的21543的下一个排列。参考实现代码如下：

<?php

$str = '21543';
$length = strlen($str);
$i = $length - 2;
while ($i >= 0) {
    if ($str[$i] < $str[$i+1]) {
        break;
    }
    $i--;
}

if ($i < 0) {
    echo  '当前字符串已经为最大';
    return false;
}

$k = $length -1;
while ($k > $i && $str[$k] <= $str[$i]) {
    $k--;
}

// 交换i和k的值
$temp = $str[$i];
$str[$i] = $str[$k];
$str[$k] = $temp;

// 反转i以后的字符串
$newStr = substr($str, 0, $i + 1) . strrev(substr($str, $i + 1));
var_dump($newStr);