how to enumerate/generate all possible binary trees from N leaves and N-1 nodes?

Question

I am trying to implement the 24 Game in ansi C. This game goes as follows:

For a list of four given numbers, try to find a solution involving these four numbers, that, using addition(+), subtraction(-), multiplication(*) and division(/) ends up at 24. Each number can only appear once, but the order of the numbers might be changed of course. It is possible to use brackets to change the order of the operands (and you have to do so for many of the solutions).

I wanted to build on top of this problem, and invent a M Game, where M can be an arbitrary number, and you can give an arbitrary length N list of values.

What I know:

• Operators can be re-used multiple times in the formula. Thus, when iterating over the operators, I can just use flags to check if a certain operator should be used at a certain place.
• Numbers can only be used once. There exist great tutorials out there that explain how to permute an array until all different orders have been exhausted.

However, what I still am having trouble with, is how to decide the different combinations of operators.

Say I have a function

op(A, B)

This function is non-commutative, e.g. op(A,B) != op(B,A). Now, if I have four values, I want to know in what ways I need to combine these functions. I know that the sequence of Catalan numbers tells us how many options there are. (for four numbers, there are 5 sequences). These are:

1. op(A, op(B, op(C,D)))
2. op(op(op(A,B),C),D)
3. op(op(A,op(B,C),D))
4. op(A,op(op(B,C),D))
5. op(op(A,B),op(C,D))

Using a simple bitVector with recursion I am able to find the first four. But not the fifth, where two nodes share the same 'level'.

Is there an iterative way to test all these different options?

Or, as Ordous aptly put it:

how to enumerate/generate all possible binary trees from N leaves and N-1 nodes?

Answer 1

Define a recursive function that takes an array of values and will generate a list of all the trees we want.

When the function receives just one value, it should return a list containing as it's sole element that value.

When the function receives two values, it should returns list containing as it's sole element the op of those two values in order.

When the function receives more than two values, it should keep a list to return, and iterate through the indices between the members of the array. For each index between members of the array, split the array into a left array and a right array based on the index. Recurse on these arrays, generating the list of trees for each. Then take the cross product of the lists this generated and add it to the list to return.

The way this works is that for any array of more than two values, we can split it multiple ways. For each way to split the array, there is at least one possible tree on the left side, and at least one possible tree on the right side. Each combination of possible trees on the right and left sides is a possible tree.

Edit: Here's some pseudo code (roughly Java/python):

List<Tree> getOpTrees(List<Value> values):
    if (length(values) == 1):
        return new List(new IdentityTree(values[0]))
    if (length(values) == 2):
        return new List(new OpTree(values[0], values[1]))
   treeList = new List<Tree>()
   for (index from 1 to length(values)-1):
       leftList, rightList = values.split(index)
   for (leftTree : getOpTrees(leftList)):
   for (rightTree : getOpTrees(rightList)):
        treeList.add(new OpTree(leftTree, rightTree))
return treeList

Actually, I don't think we even need the n=2 base case. If n=2, we will only ever have index=1. Then we split the left and right lists, which will each have exactly one element. They will each return a single element list containing the identity tree of their element. Then the only thing added to treeList will be OpTree of the two IdentityTrees.