用于查找给定字符串的下一个更大排列的算法

Question

我想要一个有效的算法来找到给定字符串的下一个更大的排列.

Answer 1

维基百科有一篇关于字典顺序生成的好文章.它还描述了生成下一个排列的算法.

引用:

以下算法在给定排列后按字典顺序生成下一个排列.它就地改变了给定的排列.

1. 找到最高指数i,使得s[i] < s[i+1].如果不存在这样的索引,则排列是最后的排列.
2. 找到最高指数j > i,使得s[j] > s[i].这样的j必须存在,因为i+1这样的指数.
3. 交换s[i]使用s[j].
4. 将索引后的所有元素的顺序颠倒i到最后一个元素.

Answer 2

这里描述了一个很好的解决方案:https://www.nayuki.io/page/next-lexicographical-permutation-algorithm.并且,如果存在下一个排列,则返回它的解决方案,否则返回false:

function nextPermutation(array) {
    var i = array.length - 1;
    while (i > 0 && array[i - 1] >= array[i]) {
        i--;
    }

    if (i <= 0) {
        return false;
    }

    var j = array.length - 1;

    while (array[j] <= array[i - 1]) {
        j--;
    }

    var temp = array[i - 1];
    array[i - 1] = array[j];
    array[j] = temp;

    j = array.length - 1;

    while (i < j) {
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
        i++;
        j--;
    }

    return array;
}

Answer 3

使用@Fleischpfanzerl 引用的来源

下一个词典排列

我们按照以下步骤找到下一个字典排列：

nums = [0,1,2,5,3,3,0]
nums = [0]*5
curr = nums[-1]
pivot = -1
for items in nums[-2::-1]:
    if items >= curr:
        pivot -= 1
        curr = items
    else:
        break
if pivot == - len(nums):
    print('break')     # The input is already the last possible permutation

j = len(nums) - 1
while nums[j] <= nums[pivot - 1]:
    j -= 1
nums[j], nums[pivot - 1] = nums[pivot - 1], nums[j]
nums[pivot:] = nums[pivot:][::-1]

> [1, 3, 0, 2, 3, 5]

所以这个想法是：这个想法是按照步骤 -

1. 从数组的末尾找到一个索引 'pivot'，使得 nums[i - 1] < nums[i]
2. 找到索引 j，使得 nums[j] > nums[pivot - 1]
3. 交换这两个索引
4. 从枢轴开始反转后缀

Answer 4

在家工作？反正可以看看C++函数std::next_permutation，或者这个：

http://blog.bjrn.se/2008/04/lexicographic-permutations-using.html