Permuting a binary tree without the use of lists

Question

I need to find an algorithm for generating every possible permutation of a binary tree, and need to do so without using lists (this is because the tree itself carries semantics and restraints that cannot be translated into lists). I've found an algorithm that works for trees with the height of three or less, but whenever I get to greater hights, I loose one set of possible permutations per height added.

Each node carries information about its original state, so that one node can determine if all possible permutations have been tried for that node. Also, the node carries information on weather or not it's been 'swapped', i.e. if it has seen all possible permutations of it's subtree. The tree is left-centered, meaning that the right node should always (except in some cases that I don't need to cover for this algorithm) be a leaf node, while the left node is always either a leaf or a branch.

The algorithm I'm using at the moment can be described sort of like this:

if the left child node has been swapped
      swap my right node with the left child nodes right node
      set the left child node as 'unswapped'
  if the current node is back to its original state
      swap my right node with the lowest left nodes' right node
      swap the lowest left nodes two childnodes
      set my left node as 'unswapped'
      set my left chilnode to use this as it's original state
      set this node as swapped
      return null
  return this; 
else if the left child has not been swapped
  if the result of trying to permute left child is null
     return the permutation of this node
  else 
     return the permutation of the left child node
if this node has a left node and a right node that are both leaves
   swap them
   set this node to be 'swapped'

The desired behaviour of the algoritm would be something like this:

            branch
             /    |
       branch     3
         /   |
   branch    2
   /     |
  0      1


            branch
             /    |
       branch     3
         /   |
   branch    2        
   /     |
  1      0           <-- first swap



            branch
             /    |
       branch     3
         /   |
   branch    1         <-- second swap
   /     |
  2      0



            branch
             /    |
       branch     3
         /   |
   branch    1         
   /     |
  0      2   <-- third swap


            branch
             /    |
       branch     3
         /   |
   branch    0   <-- fourth swap        
   /     |
  1      2

and so on...

Sorry for the ridiculisly long and waddly explanation, would really, really apreciate any sort of help you guys could offer me.

Thanks a bunch!

Answer 1

What is wrong with making a list of all items in the tree, use generative means to build all possible orders (see Knuth Vol 4), and then re-map them to the tree structure?

Answer 2

The structure is just completely unsuited for permutations, but since you know it's left-centered you might be able to make some assumptions that help you out.

I tried working it in a manner similar to yours, and I always got caught on the fact that you only have a binary piece of information (swapped or not) which isn't sufficient. For four leaves, you have 4! (24) possible combinations, but you only really have three branches (3 bits, 8 possible combinations) to store the swapped state information. You simply don't have a place to store this information.

But maybe you could write a traverser that goes through the tree and uses the number of leaves to determine how many swaps are needed, and then goes through those swaps systematically instead of just leaving it to the tree itself.

Something like

For each permutation
   Encode the permutation as a series of swaps from the original
   Run these swaps on the original tree
   Do whatever processing is needed on the swapped tree

That might not be appropriate for your application, but you haven't given that many details about why you need to do it the way you're doing it. The way you're doing it now simply won't work, since factorial (the number of permutations) grows faster than exponential (the number of "swapped" bits you have). If you had 8 leaves, you would have 7 branches and 8 leaves for a total of 15 bits. There are 40320 permutation of 8 leaves, and only 32768 possible combinations of 15 bits. Mathematically, you simply cannot represent the permutations.