What python code generates all possible groupings (trees) for binary operators

As explained in several SO questions, and more abstractly at mathworld, the sequence of Catalan numbers happens to correspond to the number of parenthetical groupings that can be generated for any given number of operators. But I haven’t found an algorithm to generate all these groupings.

This binary bracketing algorithm corresponds to the Tamari Lattice and can be described in a number of different ways. The most obvious practical use for this algorithm is to generate all possible expressions by every possible bracketing around binary operators and the numbers they operate on. This can be used to exhaustively test various types of operations on binary trees.

Web searching did reveal one implementation in C# but I think it would take me a while to understand as I don’t know C# syntax.

So, what python code generates all the possible groupings of parenthesis around operators (which can thus be used with an actual expression to generate all the possibilities)? Output would look as follows for 2, 3, and 4:

AllBinaryTrees(2)

  1. (x(xx))
  2. ((xx)x)

AllBinaryTrees(3)

  1. (((xx)x)x)
  2. ((x(xx))x)
  3. ((xx)(xx))
  4. (x((xx)x))
  5. (x(x(xx)))

AllBinaryTrees(4)

  1. (x(x(x(xx))))
  2. (x(x((xx)x)))
  3. (x((xx)(xx)))
  4. (x((x(xx))x))
  5. (x(((xx)x)x))
  6. ((xx)(x(xx)))
  7. ((xx)((xx)x))
  8. ((x(xx))(xx))
  9. (((xx)x)(xx))
  10. ((x(x(xx)))x)
  11. ((x((xx)x))x)
  12. (((xx)(xx))x)
  13. (((x(xx))x)x)
  14. ((((xx)x)x)x)

Even better would be code which did something like the following:

AllBinaryTrees(“2+3/4”)

output:

  1. 2+(34)
  2. (2+3)/4

Best answer

How about

def allbinarytrees(s):
    if len(s) == 1:
        yield s
    else:
        for i in range(1, len(s), 2):
            for l in allbinarytrees(s[:i]):
                for r in allbinarytrees(s[i+1:]):
                    yield '({}{}{})'.format(l, s[i], r)

Sample usage:

for t in allbinarytrees('1+2-3*4/5'):
    print(t)

Output:

(1+(2-(3*(4/5))))
(1+(2-((3*4)/5)))
(1+((2-3)*(4/5)))
(1+((2-(3*4))/5))
(1+(((2-3)*4)/5))
((1+2)-(3*(4/5)))
((1+2)-((3*4)/5))
((1+(2-3))*(4/5))
(((1+2)-3)*(4/5))
((1+(2-(3*4)))/5)
((1+((2-3)*4))/5)
(((1+2)-(3*4))/5)
(((1+(2-3))*4)/5)
((((1+2)-3)*4)/5)