Generate all possible permutations of a string in C++

Question

This is my version of the possible permutations of a string challenge. Please give me feedback or criticism. There are two vectors here: positions and pointed_to. positions[i] holds the index of the i'th character in the permutation. pointed_to[i] is true if the index of the i'th character in the original string is present somewhere inside the positions vector. I like to think of the positions vector as "character pointers". There are as many "character pointers" as there are characters in the original string. Each "character pointer" points to a character in the original string. The position[0] "points to" the first character in the permutation, the position[1] "points to" the second character in the permutation, and so on.

Inside the function, there is a loop which picks a char in the original string for each "character pointer" to "point to". Each char in the string can be pointed to by no more than one "character pointer". So we are looping until we find an open position for that "character pointer", a char to which no other pointers point to, pointed_to = false.

The position array is pass by reference, or it could be a global variable, because we don't care about storing the previous states of it's data in the recursion stack. Each newly created stack frame finds a position for the 0'th "pointer". This corresponds to position[0]. As the recursive stack grows, it fills in position[1], then position[2], [3], ... and so on. When stack frames get popped off the stack, we no longer care about the "residue" left in position[ the higher insides ]. This is similar in principle to how stack frames in the real recursive stack are not deleted, but simply considered as garbage values. All values position[a] where a > current_position are also considered to be garbage values. When the stack grows to be the size of the string, all the positions will have been filled up anyway, and so we can just print the permutation by following the pointers.

The pointed_by array is stored on the stack, however, and it is passed by value. In positions, only a single element was considered to be data associated with the current stack frame, so we could place it outside the stack. However, the whole pointed_by array is considered to be data associated with the current stack frame. That way when the stack frames are being popped off, we preserve the whole old state of the pointed_to array as it was originally.

I know that this explanation sounds kind of confusing, so sorry about that. Well, this algorithm actually works, and only O(n) memory is taken up.

#include <cstdlib>

#include <iostream>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using std::string;
using std::vector;


template <typename TYPE>
void print_vector(vector<TYPE> vect)
{
    for (auto x : vect) {
        cerr << x << ' ';
    }
}


void print_permutations(const string& input,
                        vector<int>& positions, vector<bool> pointed_to,
                        size_t current_position, size_t string_length)
{
    if (current_position == string_length) {
        for (size_t i = 0; i < string_length; ++i) {
            cout << input.at( positions.at(i) );
        }
        cout << endl;

        return;
    }

    for (size_t i = 0; i < string_length; ++i) {
       // not empty
       if (pointed_to.at(i)) {
            continue;
        // empty
        } else {
            positions.at(current_position) = i;
            pointed_to.at(i) = true;
            print_permutations(input, positions, pointed_to, current_position + 1, string_length);
            pointed_to.at(i) = false;
        }
    }

    return;
}


int main()
{
    string input;
    cout << " > ";
    cin >> input;

    cout << endl;

    size_t string_length = input.length();

    vector<int> positions(string_length);
    vector<bool> pointed_to(string_length, false);

    print_permutations(input, positions, pointed_to, 0, string_length);

    return EXIT_SUCCESS;
}

Answer 1

I see you have using declarations to bring names from the std namespace into your program. However, you appear to have missed std::size_t, which you seem to assume is in the global namespace (it might be, with your compiler, but that's a non-portable assumption).

I didn't completely follow the logic of the implementation. Every time I tried to read it, I just wondered why you're not using std::next_permutation() from the <algorithm> library.

Answer 2

• Trust yourself. There is no chance to have an out-of-bounds access to any of your vectors. Testing it with .at() is a pure waste of cycles. Prefer [].

• Structuring code like

      if (pointed_to.at(i)) {
          continue;
      } else {
          do_real_job;
      }
  

  looks anti-idiomatic. Either drop else to un-indent:

      if (pointed_to.at(i)) {
          continue;
      }
      do_real_job;
  

  or negate the condition:

      if (!pointed_to.at[i]) {
          do_real_job;
      }
  

• The print_permutations interface requires an intimate knowledge of implementation, and forces the caller to allocate two vectors which are of no interest to her. Consider wrapping it in

  print_permutations(const string& input) {
      size_t length = input.length();
  
      vector<int> positions(string_length);
      vector<bool> pointed_to(string_length, false);
  
      print_permutations(input, position, pointed_to, 0, length);
  }
  

  with an overloaded variant being private to implementation.

• size_t string_length = input.length(); assumes that the type of the result of string::length() is size_t. Usually it is the case, but the only guarantee is that it is some unsigned integer type. You can use it as std::string::size_type string_length. In C++11 auto string_length works as well.

• print_vector is never used.

Answer 3

I understand that this is a code challenge, i.e a somewhat artificial exercise meant to show / test / improve your proficiency. But if you want the challenge to be more meaningful and challenging, you should consider it from a broader point of view: how user-friendly is my interface? is it extensible? is it idiomatic? does it fit nicely with the language concepts and abstractions?

I suspect you already know that your interface will discourage most users. It should be a lot more concise: void print_permutations(const std::string& src). But once you have offered a smooth interface, there is, especially in C++, a kind of promise you need to keep: don't make the user pay a price he wasn't warned about. But allocating two vectors the size of the original string is a price most of us wouldn't pay when it's well known there are efficient in-place algorithms.

In-place permutations

There are several strategies to achieve in-place permutations. One of the most efficient, without being complex at all, is Heap's algorithm. It's the first one to study (and I believe studying great algorithms is as profitable as devising your own). You could also take a look at the STL's approach: STL's algorithms generally are stateless and std::next_permutation is: it doesn't rely on a counter as Heap's algorithm, but generates the next permutation in the lexicographical order.

It's the first reason I would advise for a rewriting of your algorithm. The second is that it lacks orthogonality: printing and permuting are orthogonal tasks that should be separated.

Orthogonality

One of the most powerful concept behind C++ is generic programming. You don't code a vector of ints but a vector for an arbitrary type, for instance. And yet more interestingly, you don't code an algorithm for a specific purpose but for a generic one: in this case, not for printing every permutation, but for applying some function to every permutation. And while we're at it, we should be able to compute permutations of any string-like container.

That's why I would suggest another interface:

template <typename Iterator, typename Function>
Function for_each_permutation(Iterator first, Iterator last, Function fn);

Concrete implementation tips

Apart from @vpn's advice:

use range-based for loops:

for (size_t i = 0; i < string_length; ++i) {
    cout << input.at( positions.at(i) );
} // a bit ugly

for (auto pos : positions)
    std::cout << input[pos]; // nicer

don't abuse using directives. It's a nice effort not to import the whole namespace, but that long a list of usings will be hard to maintain properly. Typing std:: is a pain only the first few hundred times, after that you don't think about it anymore.