我正在嘗試實作 std::next_permutation(std::string w) 演算法。請參閱下面的代碼以了解我是如何執行此操作的：
<!-- language-all: cpp -->
string biggerIsGreater(string w) {
// 1. Find the largest non-increasing suffix. This suffix already has the maximum permutation.
// 2. Assign the char before that as the pivot
// if there is no such char,
// then the whole string is non-increasing => no next permutation.
// 3. Swap the pivot with the smallest element in the suffix that is greater than the pivot itself.
// If there are multiple smallest char > pivot, then choose the rightmost one
// As this will keep the suffix non-increasing.
// 4. reverse the order of the suffix, so that it is now non-decreasing.
// This is the lowest next permutation.
// 1.
int suffix_start = (int)w.length()-1;
//single character has no next permutation:
if (suffix_start == 0) return "no answer";
// else keep decreasing suffix_start until the element is not > the previous.
while(w[suffix_start-1] <= w[suffix_start]) {
suffix_start--;
if(suffix_start==0) return "no answer";
}
// 2.
int pivot = suffix_start - 1;
// 3.
int smallest_char = (int)w.length()-1;
while(w[smallest_char] <= w[pivot]) smallest_char--;
if(w[smallest_char] == w[smallest_char-1]) while (w[smallest_char] != w[smallest_char-1]) smallest_char--;
swap(w[pivot], w[smallest_char]);
// 4.
reverse(w.begin() pivot 1, w.end());
return w;
}
但是，此代碼似乎在 'bb' 之類的字串上失敗。請你能告訴我哪里出錯了嗎？
所以如果我在反轉后列印出 w ，我會得到這個錯誤：--第一行是測驗用例的數量：輸入：
5 ab bb hefg dhck dkhc
然后程式列印 ba （這意味著第一個作業）但沒有列印任何其他內容。
所以錯誤在于處理bb。
注意：我的目標是在沒有庫中的 std::next_permutation() 函式的情況下撰寫這個。
謝謝
uj5u.com熱心網友回復：
我以自己的方式重新實作了您的功能，如果它不是一個可以接受的答案，那么至少它對教育目的是有益的。也許通過我的代碼，您可以弄清楚您的代碼有什么問題。
如果這是最后一個排列，就像"bb"case 一樣，則回傳第一個字典排列，與std::next_permutation()相同。
在線嘗試！
#include <string>
#include <iostream>
std::string next_permutation(std::string x) {
if (x.size() <= 1)
return x;
std::ptrdiff_t i = 0, j = 0;
for (i = x.size() - 2; i >= 0 && x[i] >= x[i 1]; --i);
if (i >= 0) {
for (j = i 1; j < x.size() && x[i] < x[j]; j);
--j;
std::swap(x[i], x[j]);
}
std::reverse(&x[i 1], &x[x.size()]);
return x;
}
int main() {
auto Test = [](auto const & s){
std::cout << "'" << s << "' -> '"
<< next_permutation(s) << "'" << std::endl;
};
Test("ab");
Test("bb");
Test("hefg");
Test("dhck");
Test("dkhc");
Test("abc");
Test("aabb");
Test("cba");
}
輸出：
'ab' -> 'ba'
'bb' -> 'bb'
'hefg' -> 'hegf'
'dhck' -> 'dhkc'
'dkhc' -> 'hcdk'
'abc' -> 'acb'
'aabb' -> 'abab'
'cba' -> 'abc'
uj5u.com熱心網友回復：
這是@Arty 的解決方案。所以完全歸功于他。
我添加了評論來嘗試解釋它是如何作業的，以便我能更好地理解它。
#include <string>
#include <iostream>
std::string next_permutation(std::string x) {
std::ptrdiff_t i = 0, j = 0;
// start with penultimate element
// as long as i doesn't hit the start and the sequence is non-increasing, keep decreasing i.
// the value of i we reach is the first element from the right which is not in reverse order (=> the maximum permutation)
// this is the pivot
for (i = x.size() - 2; i >= 0 && x[i] >= x[i 1]; --i);
// if the whole array is reverse order, there is no maximum permutation.
if (i < 0)
return {};
// then find the first element after i which is less than x[i].
for (j = i 1; j < x.size() && x[i] < x[j]; j);
// stop at the next element -- I like this as it avoids the problem of acccb, if a is the pivot
// then this code will stop at the first c.
--j;
// swap the elements
std::swap(x[i], x[j]);
// reverse the remaining array in order to minimise it, as we know it is in descending order.
std::reverse(&x[i 1], &x[x.size()]);
return x;
}
int main() {
auto Test = [](auto const& s) {
std::cout << "'" << s << "' -> '"
<< next_permutation(s) << "'" << std::endl;
};
Test("abc");
Test("bb");
Test("aabb");
Test("cba");
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/455262.html