How-To Bracket all Possible Evaluations of a Binary Operator for an Arbitrary Input Length

What will we cover in this tutorial?

Consider addition of the following expression. 5 + 7 + 3. As addition is associative, the order of evaluation does not matter. Hence, we have that (5 + 7) + 3 = 5 + (7 + 3).

For an arbitrary binary operator op(x_1, x_2) -> y, you cannot assume that op(x_1, op(x_2, x_3)) = op(op(x_1, x_2), x_3). Hence, the order of evaluation of a binary operator matters.

The brackets give the order of how the expression is evaluated. Hence, if an operator takes three different inputs, a, b, or c, then we can write a(ab), to symbol it evaluated ab first, then the result of ab with a.

This tutorial will show you how to get all possible evaluations of an arbitrary length input. That is, given an input, e.g., abab, how to find a list of all possible evaluations of the input, [(a(b(ab)), (a((ba)b), (ab)(ab), ((a(ba))b), (((ab)a)b)].

Consider that for a moment. How do you program that in Python?

Step 1: Define the problem

For simplicity we assume we have a binary operator op: [a, b, c] x [a, b, c] -> [a, b, c]. The operator can take arguments op(a, b) and evaluate it and give, say, c.

To make that notation more efficient, we will write op(ab) = c. If we make an evaluation table of the operator, say, we will have the following.

opabc
accb
bacb
cbaa
Evaluation of the operator op.

Hence, we have that op(aa) = c, op(ab) = c, …, op(cc) = a.

Now notice, that this operator is not associative or commutative.

It is not commutative, as op(ab) ≠ op(ba).

And it is not associative, as op(a op(ac)) = op(ab) = c ≠ op(op(aa) c) = op(cc) = a.

Now we understand why a binary operator needs an order of evaluation. Because, the final output will depend on it.

What we want now, is given an input, e.g., aac, how many ways can you set brackets to get a different evaluation of a binary operator, [(a(ac), ((aa)c)].

Step 2: Breaking the problem down

Now we understand why the problem is important. But how do we solve it?

Breaking it down and think like a programmer.

The base case is a string of length 2, e.g., aa, which only has one possible way (aa).

Then we have the case of length 3, e.g. aac, which can be broken down into two ways ((aa)c), (a(ac). Another way to think of it, is you can break a string of length 3, into a string of length 2 + 1 or 1 + 2.

Then the case of length 4, say, aaab, that can be broken down into (((aa)a)b), ((a(aa))b), ((aa)(ab)), (a((aa)b)), (a(a(ab))). Or you could think of it like, 3 + 1, 2 + 2, 1 + 3. Wait, what does that mean?

A drawing might come in handy now.

A visualization of the way to break down the bracket problem

See, a string of length 4 can be broken down into an instance of length 1 (as the first argument to the operator) and length 3, an instance of length 2 and 2 (each as input to the operator), or of length 3 and 1 (each as input to the operator).

Hence, you break the problem recursively down.

For a string of length 5 you have the following diagram.

A string of length 5

Amazing. Now we just need to turn that into code.

Step 3: How to create a list of all possible brackets for a binary operator

Consider the diagram from last step. Then think about recursion. How do they all add up together?

Recursion, you need a base case. It could be for a string of length 2, but let’s do it for length 1 instead, as you see you want to call for length 1.

def get_all_variations(x):
    if len(x) == 1:
        return [x]
    solutions = []
    for i in range(1, len(x)):
        x1 = x[:i]
        x2 = x[i:]
        res1 = get_all_variations(x1)
        res2 = get_all_variations(x2)
        for r1 in res1:
            for r2 in res2:
                solutions.append('(' + r1 + r2 + ')')
    return solutions

res = get_all_variations('aaabc')
for r in res:
    print(r)

This shows how to create it simple with an example. The function has the base case, where it just returns the element in a string. In the general case, it breaks the string down into two non-zero length string. Then it calls recursively.

For each of the results, it appends all possible solutions together in all possible ways.

The above code gives the following output.

(a(a(a(bc))))
(a(a((ab)c)))
(a((aa)(bc)))
(a((a(ab))c))
(a(((aa)b)c))
((aa)(a(bc)))
((aa)((ab)c))
((a(aa))(bc))
(((aa)a)(bc))
((a(a(ab)))c)
((a((aa)b))c)
(((aa)(ab))c)
(((a(aa))b)c)
((((aa)a)b)c)

Conclusion

This is an amazing example of how to solve a computer science problem. The method is a general way to break down into a recursive function. Learning the skills in this tutorial is crucial to become a good problem solver in computer science.

Leave a Reply

%d bloggers like this: