Permutations of a binary tree.

Question

Consider a binary tree:

1. n is a node, if n is an integer
2. (+ a b) is a node, if a and b are nodes.

We have the following three operations:

1. (+ a b) -> (+ b a)
2. (+ (+ a b) c) -> (+ a (+ b c))
3. (+ a (+ b c)) -> (+ (+ a b) c) -- (2. in reverse)

I need an algorithm for giving all the possible permutations of a given tree using these operations. Any operation maybe applied to any subtree. With a permutation I mean any tree that has the exact same set of leaves. It's probably not very difficult, but I just can't seem to figure it out.

[Edit] The leaves can also be names (i.e. variables), so relying on their properties as integers is not an option. The trees do represent sums.

[Edit2] The point of this excercise is to reduce a sum by finding terms of the form A and -A, swizzling the tree to get them into a subtree (+ A -A) in order to eliminate them. The three operations above are axioms in my system and they need to be used all the way, otherwise it's not possible to prove that the reduced tree is equal to the original. Since I'm using Twelf logic programming language, if I can figure out an algorithm to do what I originally asked, the rest follows easily, but alternative solutions are of course welcome.

Answer 1

The solution to this problem is undoubtably going to include Catalan numbers. There are C_n-1 possible binary trees with n leaves, and there are n! possible orderings of the leaves, so there are n! * C_n-1 possible trees. Enumerating them is slightly trickier, though.

Answer 2

These operations are analogous to addition with the following properties: closure, associativity, commutativity. For a matching node, each leaves the set of leaves the same, and can be applied in a recursive fashion. To count the permutations of a given node x (in some strange mix of Haskell and F#)

let count x = match x with
  | LeafNode -> 1
  | TreeNode (a,b) -> 2 * count a * count b

Answer 3

Seems like the most straightforward solution would be a depth-first traversal of your tree to collect all of the nodes into a list, generate all of the permutations of list, dump each permutation into binary tree.

So, given the list (+ a (+ b c) ), we have the nodes [a; b; c], which have the following permutations:

[a; b; c]
[a; c; b]
[b; a; c]
[b; c; a]
[c; a; b]
[c; b; a]

The first item in the list is your head, the following two items are the child nodes, the next four items are the child-child nodes, and so on.

The complexity of this increases dramatically if you need produce a list of all possible trees, rather than just balanced ones. In that case, you'd need to group them like this:

[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; d; c]
// first permutation
[(a; b); d; c]
[(a; b; d); c]
...

Where each n-tuple is a set of nodes. For more than a few nodes, the universe will experience a heat-death before your algorithm ever completed.

Answer 4

You have associativity and commutativity, so you can move elements around freely. A practical approach to this problem is something like the following:

• Comb the tree to one side, you get a list.

• Sort the list, so that the elements that should cancel out are next to each other.

• Move the elements into a subtree and cancel.

To get your desired proof you have to build small proofs for these operation which you then combine.

Alternatively you could look up AC-matching.

Trying all permutations as you suggest will just get you a big combinatorical explosion.

Answer 5

As pointed out, if you really have the commutativity and associativity axioms, you are best off by just collecting the summands and processing them as a set or a list.

If that's not satisfactory, the next thing is to observe that actually you do not seem to need all the permutations, but you want to rewrite your expressions in order to simplify them. That can be made much more efficient than producing all the permutations!

However, to repeat :), if you ONLY have commutativity and associativity, process the terms in a set.

Answer 6

I've discovered a solution to the underlying problem of reducing trees:

1. Find a pair of leaves A and -A from the tree.
2. a) If A and -A are in the same child, recurse.
3. b) 'Bubble' A and -A to the top of their respective childs. There are eight possible resulting cases, but they all look something like this (+ (x A) (-A y)). Going from that to (+ (+ x y) (+ A -A)) is easy.

As suggested, another way to do it would be to first convert the tree into a list: (+ A (+ B (+ ...)) X), then find a matching pair A and -A and bring them to top. I suspect that this may produce a longer proof (which is undesirable) than the above algorithm, though I haven't tried it.

Still, I find the original question fascinating and I'd like to try how an algorithm based on that would compare to the above.