[翻译]基于词典序的生成下一排列算法

发表于 2017-12-13 分类于算法阅读次数：阅读次数：本文字数： 1.2k 阅读时长 ≈ 4 分钟

翻译来源https://www.nayuki.io/page/next-lexicographical-permutation-algorithm

简介

假设对于一个有限长度的数组序列(0, 3, 3, 5, 8)，需要生成对应的所有全排列。有什么好的办法做到？

最原始的方案是使用自顶向下的递归方式。首先选举出第一个位置的元素，然后递归选择第二个元素从剩下的元素中，直到剩余一个元素。但是这种方法很复杂因为它需要递归、堆栈存储和去重。而且，如果坚持操作序列（不使用临时数组），那么这种方法在生成字典序排列的使用会有很大的困难。

最有效生成所有排列的方式是以字典序最小的开始，重复进行计算下一个排列。这个简单而又快速的算法将在本页进行阐述。我们将会使用具体的例子来解释算法的每一个步骤。

算法描述

序列(0, 1, 2, 5, 3, 3, 0)作为测试数据。

本算法的关键步骤是当我们计算生成下一个排列时，必须尽可能小的增加序列值。就像我们数数一样，我们总是尽可能的去修改最右侧（低位）的数据，保持左侧（高位）的数字不动一样。例如：从{0,1}到{0,2}，完全不需要将第一个元素从0改到1,改动第二个元素将获得更小的增加。事实上，第二个元素也无需改动，这将是接下来要说明的。

首先，标记出最长的非升序后缀子串（微弱下降）。在例子中这个后缀子串就是(5, 3, 3, 0)。最长非升序后缀已经是后缀串所有排列中的最大排列了，所以不可能计算它的下一个组合，如果要获得下一个组合，就必须和左侧的元素作出交换。（标记最大非升序后缀字串可以在通过从右往左搜索在O(n)时间内完成，还有后缀至少含有一个元素，因为一个元素的子串是非升序的）。

第二步，取出后缀子串左侧紧邻的元素（本例子中是2）称之为pivot。（如果没有这个元素，那就说明整个字串是非升序的，那么这个字符串就是最大的子串了）。pivot 必须小于后缀子串的第一个元素（5),故后缀中存在部分元素大于pivot.当我们把pivot和后缀中的大于pivot的最小元素进行交换后，就得到了最小的目标前缀。（前缀就是序列中去掉后缀的部分）。在这个例子中，最终得到了前缀(0, 1, 3)和更新后的后缀(5, 3, 2, 0)。（如果后缀有多个可选项，那就要选择最右侧的选项，接下来进入下一步。）

最后，对后缀进行非降序排序，因为前一步已经增大了前缀，所有我们希望后缀尽可能的小。事实上，完全可以避免排序而是进行简单的倒置后缀，原因在于替换元素没有改变排序。这样就得到了序列(0, 1, 3, 0, 2, 3, 5)就是我们想要计算出的的下一个排列。

简明的数学描述：

找出最大的索引i 确保有array[i − 1] < array[i]（如果不存在i,那说明序列已经是最大排列）

找出最大索引 j 使得 j ≥ i 同时 array[j] > array[i − 1]。

交换array[j] 和 array[i − 1]。

倒置以array[i]开头的后缀子串。

如果你真的读懂了这个算法，这里还有一个拓展练习：设计一个算法计算出前一个最大的字典序排列。

样例代码 (Java)

boolean nextPermutation(int[] array) {
    // Find longest non-increasing suffix
    int i = array.length - 1;
    while (i > 0 && array[i - 1] >= array[i])
        i--;
    // Now i is the head index of the suffix

    // Are we at the last permutation already?
    if (i <= 0)
        return false;

    // Let array[i - 1] be the pivot
    // Find rightmost element that exceeds the pivot
    int j = array.length - 1;
    while (array[j] <= array[i - 1])
        j--;
    // Now the value array[j] will become the new pivot
    // Assertion: j >= i

    // Swap the pivot with j
    int temp = array[i - 1];
    array[i - 1] = array[j];
    array[j] = temp;

    // Reverse the suffix
    j = array.length - 1;
    while (i < j) {
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
        i++;
        j--;
    }

    // Successfully computed the next permutation
    return true;
}