我想要一个高效的算法来找到给定字符串的下一个更大的排列。
发布于 2015-07-01 02:40:24
这里描述了一个很好的解决方案: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;
}
发布于 2009-10-26 07:57:24
家庭作业?无论如何,可以查看C++函数std::next_permutation,或者如下所示:
http://blog.bjrn.se/2008/04/lexicographic-permutations-using.html
发布于 2014-09-26 21:58:27
我们可以使用以下步骤找到给定字符串S的下一个最大的字典顺序字符串。
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. i.e., sort(S[i+1]..S[len(S) - 1])
给定的字符串是S
的下一个最大的字典顺序字符串。还可以在C++中使用next_permutation
函数调用。
https://stackoverflow.com/questions/1622532
复制相似问题