找到给定字符串的下一个更大排列的算法 [英] Algorithm to find next greater permutation of a given string

问题描述

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

解决方案

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

引用:

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

<块引用>

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

I want an efficient algorithm to find the next greater permutation of the given string.

解决方案

Wikipedia has a nice article on lexicographical order generation. It also describes an algorithm to generate the next permutation.

Quoting:

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

1. Find the highest index i such that s[i] < s[i+1]. If no such index exists, the permutation is the last permutation.
2. Find the highest index j > i such that s[j] > s[i]. Such a j must exist, since i+1 is such an index.
3. Swap s[i] with s[j].
4. Reverse the order of all of the elements after index i till the last element.

这篇关于找到给定字符串的下一个更大排列的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！