I am trying to implement a std::next_permutation(std::string w) algorithm. Please see the code below for how I am doing this:

<!-- 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;
}

However, this code appears to fail on strings like 'bb'. Please can you tell me where I have gone wrong?

So if I print out w after the reversal, I get this error: -- the first line is number of test cases: input: 5 ab bb hefg dhck dkhc

then the program prints ba (which means the first one worked) but then nothing else is printed.

So error is in dealing with bb.

note: My objective is to write this without the std::next_permutation() function from library.

Thanks

CodePudding user response：

I re-implemented your function my own way, if it is not an acceptable answer, then at least it is benefitial for educational purpose. Maybe by my code you can figure out what's wrong in yours.

If this is last permutation, like "bb" case then first lexicographical permutation is returned, same as in std::next_permutation().

Try it online!

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

Output:

'ab' -> 'ba'
'bb' -> 'bb'
'hefg' -> 'hegf'
'dhck' -> 'dhkc'
'dkhc' -> 'hcdk'
'abc' -> 'acb'
'aabb' -> 'abab'
'cba' -> 'abc'

CodePudding user response：

This is @Arty's solution. So full credit to him.

I added comments to try and explain how it works so that I can understand it better.

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