Menu
Consider a binary tree:
We have the following three operations:
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.
651
Definitions. A permutation tree is a labeled rooted tree that has vertex set {0,1,2,..,n} and root 0, and in which each child is larger than its parent and the children are in ascending order from the left to the right. The power of a permutation tree is the number of descendants of the root.
A BST can be traversed through three basic algorithms: inorder, preorder, and postorder tree walks. Inorder tree walk: Nodes from the left subtree get visited first, followed by the root node and right subtree.
For n = 5 --> 42 Binary Search Trees are possible.
In this program, we need to find out the total number of binary search trees can be constructed with n values. Below diagram shows a possible binary search tree with the key value as 3. So, we can construct a total of five binary search trees.
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.
66
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
