Permutation generator with OR operator
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&lt;std::string&gt; 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 &amp;word: sentence) {
    if (first)
        first = false;
    else
        std::cout &lt;&lt; " ";

    std::cout &lt;&lt; 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 &amp;sentence: sentences) {
    std::sort(sentence.begin(), sentence.end());

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