algorithm来查找给定string的下一个更大的排列

我想要一个有效的algorithm来查找给定string的下一个更大的排列。

Answer 1

维基百科在辞典生成方面有一篇不错的文章 。 它还描述了生成下一个排列的algorithm。

引用：

以下algorithm在给定排列后按照字典顺序生成下一个排列。 它在原地改变给定的排列。

1. finds[i] < s[i+1]的最高指数。 如果不存在这样的指数，排列是最后的排列。
2. find最高指标j > i这样s[j] > s[i] 。 这个j必须存在，因为i+1就是这样一个索引。
3. 用s[j]交换s[i] s[j] 。
4. 颠倒索引i之后的所有元素的顺序直到最后一个元素。

Answer 2

一个伟大的解决scheme的作品在这里描述： https : //www.nayuki.io/page/next-lexicographical-permutation-algorithm 。 如果下一个排列存在，则返回它，否则返回false的解决scheme：

 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

家庭作业？ 无论如何，可以看看C ++函数std :: next_permutation，或者这个：

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

Answer 4

我们可以使用以下步骤find给定stringS的下一个最大的字典string。

 1. Iterate over every character, we will get the last value i (starting from the first character) that satisfies the given condition S[i] < S[i + 1] 2. Now, we will get the last value j such that S[i] < S[j] 3. We now interchange S[i] and S[j]. And for every character from i+1 till the end, we sort the characters. ie, sort(S[i+1]..S[len(S) - 1]) 

给定的string是S的下一个最大的字典string。 也可以在C ++中使用next_permutation函数调用。

Answer 5

nextperm（a，n）

 1. find an index j such that a[j….n - 1] forms a monotonically decreasing sequence. 2. If j == 0 next perm not possible 3. Else 1. Reverse the array a[j…n - 1] 2. Binary search for index of a[j - 1] in a[j….n - 1] 3. Let i be the returned index 4. Increment i until a[j - 1] < a[i] 5. Swap a[j - 1] and a[i] O(n) for each permutation. 

Answer 6

我希望这个代码可能会有所帮助。

 int main() { char str[100]; cin>>str; int len=strlen(len); int f=next_permutation(str,str+len); if(f>0) { print the string } else { cout<<"no answer"; } }