## A quick note on all permutations

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 << str << 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.

## 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.
This entry was posted in Uncategorized. Bookmark the permalink.