Databases
StackOverflow2013
Postsdbo
POPermutations of a binary tree
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POPermutations of a binary tree
    text
    copied!<p>Consider a binary tree:</p> <ol> <li><em>n</em> is a node, if <em>n</em> is an integer</li> <li>(+ <em>a</em> <em>b</em>) is a node, if <em>a</em> and <em>b</em> are nodes.</li> </ol> <p>We have the following three operations:</p> <ol> <li>(+ <em>a</em> <em>b</em>) -> (+ <em>b</em> <em>a</em>)</li> <li>(+ (+ <em>a</em> <em>b</em>) <em>c</em>) -> (+ <em>a</em> (+ <em>b</em> <em>c</em>))</li> <li>(+ <em>a</em> (+ <em>b</em> <em>c</em>)) -> (+ (+ <em>a</em> <em>b</em>) <em>c</em>) <em>-- (2. in reverse)</em></li> </ol> <p>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.</p> <p>[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.</p> <p>[Edit2] The point of this excercise is to reduce a sum by finding terms of the form <em>A</em> and <em>-A</em>, swizzling the tree to get them into a subtree (+ <em>A</em> <em>-A</em>) 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 <a href="http://twelf.plparty.org/wiki/Main_Page" rel="nofollow noreferrer">Twelf</a> 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.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload