编写自定义 std::next_permutation(string) 函数

Question

我正在尝试实现类似于 std::next_permutation(std::string w) 的功能。请参阅下面的代码，了解我是如何执行此操作的：

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.

注意：我的 objective 是在 <algorithm>.

没有 std::next_permutation() 功能的情况下写的

Answer 1

我re-implemented你的功能我有自己的方式，如果它不是一个可以接受的答案，那么至少它对教育目的是有益的。也许通过我的代码你可以找出你的错误所在。

如果这是最后一个排列，如 "bb" 的情况，则返回第一个字典排列，与 std::next_permutation().

相同

Try it online!

#include <algorithm>
#include <iostream>
#include <string>

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.begin() + (i + 1), x.end());
    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'

Answer 2

这是@Arty 的解决方案。完全归功于他。

我添加了评论来尝试解释它是如何工作的，以便我能更好地理解它。

#include <string>
#include <iostream>
#include <algorithm>

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");
}

编写自定义 std::next_permutation(string) 函数

Writing a custom std::next_permutation(string) function

c++

algorithm