Permutieren einen binären Baum ohne die Verwendung von Listen

Question

Ich brauche einen Algorithmus zu finden, jede mögliche Permutation eines binären Baum zu erzeugen, und so tun müssen, ohne Listen zu verwenden (dies ist so, weil der Baum selbst Semantik und Beschränkungen trägt, die in Listen werden nicht übersetzt). Ich habe einen Algorithmus gefunden, die für Bäume mit einer Höhe von drei oder weniger funktioniert, aber wenn ich zu größeren Höhen zu bekommen, ich locker eine Reihe von möglichen Permutationen pro Höhe gegeben.

Jeder Knoten führt Informationen über seinen ursprünglichen Zustand, so dass ein Knoten bestimmen kann, wenn alle möglichen Permutationen für diesen Knoten versucht worden. Außerdem trägt der Knoten Informationen über das Wetter oder nicht, es wurde ‚ausgelagert‘, das heißt, wenn es alle möglichen Permutationen gesehen hat, davon subtree ist. Der Baum ist links zentriert, was bedeutet, dass der richtige Knoten sollte immer (außer in einigen Fällen, die ich brauche nicht für diesen Algorithmus zu decken) einen Blattknoten sein, während der linke Knoten ist immer entweder ein Blatt oder ein Zweig.

Der Algorithmus, den ich im Moment bin mit kann ein bisschen wie folgt beschrieben werden:

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'

Das gewünschte Verhalten des algoritm wäre so etwas wie dies:

            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  

und so weiter ...

Answer 1

Die Struktur ist nur völlig ungeeignet für Permutationen, aber da Sie es links zentrieren vielleicht wissen Sie in der Lage sein, einige Annahmen getroffen werden, die Ihnen helfen.

Ich habe versucht, es in einer Art und Weise ähnlich wie bei Ihnen zu arbeiten, und ich habe immer darauf gefangen, dass Sie nur eine binäre Information haben (vertauscht oder nicht), die nicht ausreichend ist. Für vier Blätter, haben Sie 4! (24) mögliche Kombinationen, aber Sie haben nur wirklich drei Zweige (3 Bit, 8 mögliche Kombinationen), die ausgetauscht Zustandsinformationen zu speichern. Sie einfach keinen Platz hat, diese Informationen zu speichern.

Aber vielleicht könnten Sie einen traverser schreiben, die durch den Baum geht und verwendet die Anzahl der Blätter, wie viele Swaps zu bestimmen, benötigt werden, und dann systematisch diese Swaps durchläuft, anstatt nur sie an den Baum verlassen sich.

So etwas wie

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

Das könnte nicht für Ihre Anwendung geeignet sein, aber Sie haben nicht, da viele Details darüber, warum Sie es die Art und Weise zu tun, müssen Sie es tun. Die Art und Weise Sie es jetzt tun wird einfach nicht funktionieren, da faktorielles (die Anzahl der Permutationen) wächst schneller als exponentiell (die Anzahl von „getauscht“ Bits Sie haben). Wenn Sie 8 Blätter haben, würden Sie 7 Niederlassungen und 8 Blätter für insgesamt 15 Bits. Es gibt 40320 Permutation von 8 Blättern, und nur 32.768 mögliche Kombinationen von 15 Bit. Mathematisch kann man einfach nicht die Permutationen darstellen.

Answer 2

Was mit der Herstellung eine Liste aller Elemente in der Struktur falsch ist, generative Mittel verwenden, um alle möglichen Befehle (siehe Knuth Band 4) zu bauen, und dann neu ordnet sie in die Baumstruktur?