A quick note on next permutation

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.

Advertisements

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s