Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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+(3/4)
  2. (2+3)/4
like image 219
Joe Golton Avatar asked Jun 21 '13 18:06

Joe Golton


2 Answers

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)
like image 63
David Eisenstat Avatar answered Nov 11 '22 05:11

David Eisenstat


The accepted answer only works for single digit numbers, and I will leave it as accepted answer because it illustrates the concept in an easy to read fashion. This modified, messier looking version works for all numbers, not just single digit numbers:

def allbinarytrees(s):
    if s.isdigit():
        yield s
    else:
        i = 0
        while i < len(s)-1:
            while i < len(s) and s[i].isdigit():
                i += 1
            if i < len(s) - 1:
                for left in allbinarytrees(s[:i]):
                    for right in allbinarytrees(s[i+1:]):
                        yield '({}{}{})'.format(left, s[i], right)
            i += 1

Sample usage:

j=0
for t in allbinarytrees('11+22*3/4456'):
    j += 1
    print j, (t[1:-1])

Output:

1 11+(22*(3/4456))
2 11+((22*3)/4456)
3 (11+22)*(3/4456)
4 (11+(22*3))/4456
5 ((11+22)*3)/4456
like image 30
Joe Golton Avatar answered Nov 11 '22 05:11

Joe Golton