3

Let's say I have the following input vectors

vector<string> variables = { "A", "B", "C", "D" };
vector<string> operators = { "+" };

As a result I would like to get all different permutations of operators between these variables. Variables are always on fixed locations - only the operators change.

For previous input vectors I need to have the following output:

A + B + C + D

This is simple as only one operator is available ("+"). But, if I have the following input vectors:

vector<string> variables = { "A", "B", "C", "D" };
vector<string> operators = { "+", "-" };

then the following output would be required:

A + B + C + D
A - B + C + D
A + B - C + D
A + B + C - D
A - B - C + D
A + B - C - D
A - B + C - D
A - B - C - D

Now I have all possible variations of those operators between variables.

So far I wrote the following function

template<class T>
vector<vector<T> > getAllPermutations(vector<T> input) {
    vector<vector<T> > res;
    do {
        vector<T> current_vector;
        for (T index : input)
            current_vector.push_back(index);
        res.push_back(current_vector);
    } while (next_permutation(input.begin(), input.end()));
    return res;
}

but this only solves part of the problem, as I don't know how to generate proper input vector each time I need to call this function.

How to solve this?

Improve this question
3
  • You don't include, for example, B - A - C + D (or equivalently, - A + B - C + D)? Commented Nov 1, 2019 at 14:05
  • @lurker Actually, no. Both situations are not possible. Variables cannot change locations. Only the operators. Commented Nov 1, 2019 at 14:11
  • The number of permutations of a sequence is (length!), but the number of choices of operators you want here is pow(number of choices, number of positions). Permutations aren't the solution; an odometer-style algorithm is. Commented Nov 1, 2019 at 15:05

3 Answers 3

Reset to default
1

EDIT: Here is another version using just loops:

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

using namespace std;

vector<string> make_combinations(
    const vector<string>& variables, const vector<string>& operators)
{
    vector<string> out;
    if (variables.empty()) return out;
    auto num_combs = pow(operators.size(), variables.size() - 1);
    out.reserve(num_combs);
    string current;
    for (size_t i_comb = 0; i_comb < num_combs; i_comb++)
    {
        current += variables[0];
        auto num = i_comb;
        for (size_t i_var = 1; i_var < variables.size(); i_var++)
        {
            current += " ";
            current += operators[num % operators.size()];
            current += " ";
            num /= operators.size();
            current += variables[i_var];
        }
        out.push_back(current);
        current.clear();
    }
    return out;
}

int main()
{
    vector<string> variables = { "A", "B", "C", "D" };
    vector<string> operators = { "+", "-" };
    auto out = make_combinations(variables, operators);
    for (const auto& str : out)
    {
        cout << str << endl;
    }
    return 0;
}

Output is the same as before, although in different order.

This is a simple recursive algorithm to do that:

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

using namespace std;

void make_combinations_rec(
    vector<string>::const_iterator varsIt, vector<string>::const_iterator varsEnd,
    const vector<string>& operators, vector<string>& out, string& current)
{
    // Add current variable
    current += *varsIt;
    auto rem = varsIt->size();
    // Check if this was the last variable
    if ((++varsIt) == varsEnd)
    {
        // Add complete expression
        out.push_back(current);
    }
    else
    {
        // For every operator
        for (auto& op : operators)
        {
            // Add operator surrounded by whitespace
            current += " ";
            current += op;
            current += " ";
            make_combinations_rec(varsIt, varsEnd, operators, out, current);
            // Remove operator
            current.erase(current.size() - op.size() - 2);
        }
    }
    // Remove variable
    current.erase(current.size() - rem);
}

vector<string> make_combinations(
    const vector<string>& variables, const vector<string>& operators)
{
    vector<string> out;
    if (!variables.empty())
    {
        // Reserve space in advance
        out.reserve(pow(operators.size(), variables.size() - 1));
        string current;
        make_combinations_rec(
            variables.begin(), variables.end(), operators, out, current);
    }
    return out;
}

int main()
{
    vector<string> variables = { "A", "B", "C", "D" };
    vector<string> operators = { "+", "-" };
    auto out = make_combinations(variables, operators);
    for (const auto& str : out)
    {
        cout << str << endl;
    }
    return 0;
}

Output:

A + B + C + D
A + B + C - D
A + B - C + D
A + B - C - D
A - B + C + D
A - B + C - D
A - B - C + D
A - B - C - D
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

For one possible solution it could help if you look at the size of operators as a numeric base and the size of variables (minus one) as the number of digits in a number represented by the base. So for you example with "+" and "-" you have two operators which means the base is 2 which is simple as it's binary arithmetic. If you have four operators (by adding e.g. "*" and "/") then the base is 4. The number of "digits" in the number you create using the base will (with your example) be variables.size() - 1, or 3.

Create the permutations using the numbers, so with the (binary) example in your question it would be

000
001
010
011
100
101
110
111

Then use the digits of this collection of numbers as translation to get the operators between each variable. That is 0 represents operators[0] which is"+" and 1 represents operators[1] which is "-".

Solving this for any generic base B and number of digits D is a little harder, but it's an old and long solved problems with plenty of descriptions, algorithms and examples available.

Improve this answer

2 Comments

That's interesting approach... And it would probably work. But I am more interested if there is some "standardized" solution already for this kind of problem.
@Tracer This is simply a base n odometer.
1

You want all permutations with repetition (a.k.a. n-tuples) of the available operators. It is very easy to write a generic function to generate all n-tuples of a given length. Here is an an iterative solution:

template <typename T>
std::vector<std::vector<T>> n_tuples(std::initializer_list<T> a, std::size_t const n)
{
    std::vector<std::vector<T>> tn = {{}};
    for (std::size_t i = 0; i < n; ++i) {
        auto tn_1 = std::move(tn);
        for (auto const& x : a) {
            for (auto const& t : tn_1) {
                t.push_back(x);
                tn.push_back(t);
            }
        }
    }
    return tn;
}

Here is how you would use it in your case:

int main()
{
    std::vector<char> vars = {'A', 'B', 'C', 'D'};
    for (auto const& ops : n_tuples({'+', '-'}, vars.size() - 1)) {
        for (std::size_t i = 0; i < ops.size(); ++i) {
            std::cout << vars[i] << " " << ops[i] << " ";
        }
        std::cout << vars.back() << "\n";
    }
}

This gives the output:

A + B + C + D
A - B + C + D
A + B - C + D
A - B - C + D
A + B + C - D
A - B + C - D
A + B - C - D
A - B - C - D

Note that n_tuples handles the case where n == 0 correctly (by returning a vector containing a single empty vector -- the 0-tuple), so it will work nicely even with a single variable.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.