1
\$\begingroup\$

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;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Some interesting things to say, I'll do a review tomorrow but I have a question, did you tried std::next_permutation ? \$\endgroup\$ – Calak Nov 14 '18 at 0:06
  • \$\begingroup\$ @Calak - No, I have not tried std::next_permutation. I don't know what that is, and anyway I don't even bother to use it because this is a coding challenge. I should solve it using my own implementation without relying on the standard library's facilities too much. \$\endgroup\$ – Galaxy Nov 14 '18 at 2:05
  • \$\begingroup\$ @Galaxy: Coding challenges are not about writing everything from scratch. They are about showing you understand the language at its standard library. As such the best solution would use the standard library function and only go to a self implemented version if that was not optimal. \$\endgroup\$ – Martin York Nov 17 '18 at 1:13
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ The question is tagged as reinvent-the-wheel and solves a coding challenge. So std::next_permutation is probably out. \$\endgroup\$ – Zeta Nov 14 '18 at 9:43
  • \$\begingroup\$ I thought that size_t is a data type that is part of the C standard library, which got "inherited" by C++. Like all names in the C standard library, not putting std:: in front of them works fine. I thought that std:: is only for names declared inside the C++ standard library, not the C one. I would like to know more about this thing. \$\endgroup\$ – Galaxy Nov 14 '18 at 22:49
  • \$\begingroup\$ size_t is defined in the global namespace if you include the C header <stdlib.h>. When you include the C++ version <cstdlib> (and I commend that choice), then C's names are defined in the std namespace, so std::size_t. Implementations are allowed, but not required to also define them in the global namespace (so it's not portable to rely in that). Does that explanation help? \$\endgroup\$ – Toby Speight Nov 15 '18 at 8:33
3
\$\begingroup\$
  • 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.

\$\endgroup\$
  • \$\begingroup\$ What does "anti-idiomatic" mean? \$\endgroup\$ – Galaxy Nov 14 '18 at 2:11
  • \$\begingroup\$ Also, what are you suggesting here "overloaded variant being private to implementation"? I don't know how to make a global function private, do you? Do you mean that the real recursive function, which is not a wrapper, should be made private? How would you accomplish that? \$\endgroup\$ – Galaxy Nov 14 '18 at 2:12
  • \$\begingroup\$ @Galaxy "Idiomatic" means "this is a way it is supposed to be done". Anti-idiomatic means the opposite; a correct code which looks strange to a professional. I don't really know how to explain it. Googling idiomatic code yields some interesting reading. \$\endgroup\$ – vnp Nov 14 '18 at 2:18
  • \$\begingroup\$ @Galaxy for your second question, consider a separate file, and declare the overloaded variant static. \$\endgroup\$ – vnp Nov 14 '18 at 2:19
  • 1
    \$\begingroup\$ An idiom is a linguistic construct. It is a common and expected way to express a very particular meaning that often only makes sense to others familiar with that language. Literal interpretations often don't translate well. @Galaxy \$\endgroup\$ – bruglesco Nov 14 '18 at 3:52
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Yes, I agree that the implementation should be changed to make it more user friendly. I have created a wrapper function designed to be used by the outside world that calls the "real function". I knew about range-based for loops, but it didn't occur to me to use them in this situation. I will look into your other suggestions, such as changing the algorithm. \$\endgroup\$ – Galaxy Nov 14 '18 at 23:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.