Marius Bancila [Bancila 2018] (Chapter 6, problem 52) poses the next permutation problem as follows:

Write a function that, prints on the console all the possible permutations of a given string.

and provides a recursive version of the solution as follows:

void next_permutation(std::string str, std::string perm)
{
if (str.empty()) std::cout << perm << std::endl;
else
{
for (size_t i = 0; i< str.size(); ++i)
{
next_permutation(str.substr(1), perm + str[0]);
std::rotate(std::begin(str),
std::begin(str) + 1,
std::end(str));
}
}
}
void print_permutations_recursive(std::string str)
{
next_permutation(str, "");
}

A better solution would be as follows

void next_permutation(std::string& str, size_t n)
{
if (n==1) std::cout << perm << std::endl;
else
{
for (size_t i = 0; i<n; ++i)
{
next_permutation(str,n-1);
std::rotate( std::end(str)-n ,
std::end(str)-n+1,
std::end(str));
}
}
}
void print_permutations_recursive(std::string str)
{
if(!str.empty())
next_permutation(str, str.length());
}

This avoids string copy over recursive calls. More importantly the second parameter

has a meaning in that it is the length of the suffix that needs to be permuted.

The other thing to notice is that `rotate`

is O(n) which can be reduced to O(1) by swapping as in

for (size_t i = 0; i < n; ++i)
{
std::swap(*(str.end()-n), *(str.end()-n+i));
next_permutation(str,n-1);
std::swap(*(str.end()-n), *(str.end()-n+i));
}

Reference

[Bancila 2018] Marius Bancila “The Modern C++ Challenge” Packt Publishing Birmingham-Mumbai 2018.

### Like this:

Like Loading...

*Related*

## About The Sunday Programmer

Joe is an experienced C++/C# developer on Windows. Currently looking out for an opening in C/C++ on Windows or Linux.