I wrote this algorithm to find the closest greater lexicographical permutation.
Given a word w, it rearranges the letters to construct another word in such a way that this new word is lexicographically greater than w. From all the possibilities the one that produces the smallest lexicographical word is chosen.

Any ideas to improve the algorithm, it's readability, or the style in general?

#include <iterator>
#include <vector>
#include <algorithm>

using namespace std;

string closest_greater_lexicographical_permutation(string w) 
 for (auto rit = next(w.rbegin()); rit!=w.rend(); ++rit) 
 auto it = prev(rit.base());
 auto lowest_max = it;
 for (auto it_max = next(it); it_max!=w.end(); ++it_max) 
 if (string(1,*it_max) > string(1,*it))
 if (lowest_max == it)
 lowest_max = it_max;
 
 else if (string(1,*it_max) < string(1,*lowest_max))
 lowest_max = it_max; 
 
 
 
 if (lowest_max != it)
 iter_swap(lowest_max, it);
 sort(next(it),w.end(),
 (auto lhs, auto rhs)
 return string(1,lhs) < string(1,rhs);
 );
 return w;
 
 
 return w;

Headers and namespaces

We don't use <vector>, but do need <string>.

Bringing all names in from a namespace is problematic; namespace std particularly so. It can silently change the meaning of your program when you're not expecting it. Get used to using the namespace prefix (std is intentionally very short), or importing just the names you need into the smallest reasonable scope.

Bug

This loop fails when w is the empty string:

for (auto rit = next(w.rbegin()); rit!=w.rend(); ++rit) {

This can be fixed with an early return:

if (w.empty())
 return w;

Algorithm

There's a standard algorithm called std::next_permutation() that does most of what we need. The one difference is that if its input is already the last permutation, it will wrap around to the first one and indicate (by its return value) that it has done so. We can use that to return the original input string in that case.

Tests

You've included no tests. I think we need to test the trivial case (empty string) and at least one case where we must return a new string and one where we already have the last possible permutation.

Improved code

#include <algorithm>
#include <string>

std::string closest_greater_lexicographical_permutation(const std::string& input) 
 auto word = input;
 return std::next_permutation(word.begin(), word.end())
 ? word // we changed it
 : input; // no change - already the last permutation


// Test program

#include <iostream>
static bool test(const std::string& input, const std::string& expected)

 auto const actual = closest_greater_lexicographical_permutation(input);
 if (actual == expected)
 return 0;

 std::cerr << "FAIL ("" << input << ""): "
 "got "" << actual << "" "
 "instead of "" << expected << """ << std::endl;
 return 1;


int main()

 return 0
 + test("", "")
 + test("aabb", "abab")
 + test("cba", "cba")
 ;