Permutation generator with OR operator

Question

Problem: Given a vector of strings, I want to print out all possible permutations where the strings may contain an OR operator (the | character, as in regular expressions).

Example Input: the strings race and car|horse

Example Output:

race car
race horse
car race
horse race

This code uses -std=c++17 and helper code from other programmers (if this makes it off topic, I will recode these parts).

This is faster than the Python version from one of my questions on a sibling site.

Code:

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>

// Begin helper function from https://stackoverflow.com/a/236803/10976976
template <typename Out>
void split(const std::string &s, char delim, Out result) {
    std::istringstream iss(s);
    std::string item;
    while (std::getline(iss, item, delim)) {
        *result++ = item;
    }
}

std::vector<std::string> split(const std::string &s, char delim) {
    std::vector<std::string> elems;
    split(s, delim, std::back_inserter(elems));
    return elems;
}
// End helper function from https://stackoverflow.com/a/236803/10976976


// Begin helper function from https://stackoverflow.com/a/17050528/10976976
std::vector<std::vector<std::string>> cart_product (const std::vector<std::vector<std::string>>& v) {
    std::vector<std::vector<std::string>> s = {{}};
    for (const auto& u : v) {
        std::vector<std::vector<std::string>> r;
        for (const auto& x : s) {
            for (const auto y : u) {
                r.push_back(x);
                r.back().push_back(y);
            }
        }
        s = std::move(r);
    }
    return s;
}
// End helper function from https://stackoverflow.com/a/17050528/10976976


int main() {
    std::vector vector_of_strings{"C++|Python|PHP", "Is|Is Not", "Good|Great|Excellent|Exceptional"};
    std::vector<std::vector<std::string>> vector_of_vector_of_strings;

    for (auto& word_possibilities_string : vector_of_strings) {
        auto word_possibilities = split(word_possibilities_string, '|');
        vector_of_vector_of_strings.push_back(word_possibilities);
    }

    // vector_of_vector_of_strings is now {{C++, Python, PHP}, {Is, Is Not}, {Good, Great, Excellent, Exceptional}}

    auto sentences = cart_product(vector_of_vector_of_strings);

    for (auto& sentence : sentences) {
        std::sort(sentence.begin(), sentence.end());

        do {
            const auto seperator = " ";
            const auto* sep = "";

            for (const auto& word : sentence) {
                std::cout << sep << word;
                sep = seperator;
            }

            std::cout << "\n";
        } while(std::next_permutation(sentence.begin(), sentence.end()));
    }
}

Output (I'm sure you'll agree with the statements below):

C++ Good Is
C++ Is Good
Good C++ Is
Good Is C++
Is C++ Good
Is Good C++
...
Exceptional Is Not PHP
Exceptional PHP Is Not
Is Not Exceptional PHP
Is Not PHP Exceptional
PHP Exceptional Is Not
PHP Is Not Exceptional

In the future, I will be reading in vector_of_strings from a file and passing in the starting permutation as arguments.

For example: ./permutation_generator words.txt PHP Exceptional "Is Not" will output:

PHP Exceptional Is Not
PHP Is Not Exceptional

Answer 1

user673679 already mentioned that a lot of string copying is going on. Indeed, std::string_view could be used here to just keep references to the original input strings, saving both time and space.

Give your variables meaningful names

Your variable names should tell you something about the contents of the variable, not of the type of the variable. So don't write std::vector<std::string> vector_of_strings, but give it a more descriptive name such as input if it's the input to your program, and possibilities instead of vector_of_vector_of_strings.

Also avoid variable names that are too alike, such as separator and sep in your main() function. In this case, you can avoid it by writing the code like so:

bool first = true;

for (const auto &word: sentence) {
    if (first)
        first = false;
    else
        std::cout << " ";

    std::cout << word;
}

Don't abbreviate too much, just write carthesian_product instead of cart_product. The latter abbreviation is not common and might confuse others that do not know that you mean Carthesian product here.

Use more algorithms?

Since you are already using some of the C++ standard library algorithms, why not use more? For example, instead of writing a for-loop to create the vector of vector of strings, write:

std::transform(input.begin(), input.end(),
               std::back_inserter(possibilities),
               [](std::string words){
                   return split(words, '|');
               });

Although arguably, it doesn't improve readability much here.

Split off more functionality into their own functions

The main() function could be cleaned up and made more readable if you moved some of its parts to properly named functions. For example, instead of creating the vector of vector of strings inline, it would be nice it you could just write:

auto possibilities = split_possibilities(input);

Also, consider creating a join() function, so writing out all the permutations could be written as:

for (auto &sentence: sentences) {
    std::sort(sentence.begin(), sentence.end());

    do {
        std::cout << join(sentence, " ") << '\n';
    } while(std::next_permutation(sentence.begin(), sentence.end());
}

Answer 2

That's a lot of unnecessary string copying.

If you change all the std::strings to std::string_view and write your own split function (simple enough using std::find) it will be much faster.