Permutant un arbre binaire sans l'utilisation de listes

Question

Je dois trouver un algorithme pour générer toutes les permutations possibles d'un arbre binaire, et la nécessité de le faire sans utiliser des listes (ce qui est parce que l'arbre lui-même porte la sémantique et les contraintes qui ne peuvent pas être traduits dans des listes). Je l'ai trouvé un algorithme qui fonctionne pour les arbres à la hauteur de trois ou moins, mais chaque fois que je reçois à de plus hauts sommets, je lâche un ensemble de permutations possibles par hauteur ajouté.

Chaque nœud porte des informations sur son état d'origine, de sorte qu'un noeud peut déterminer si toutes les permutations possibles ont été jugés pour ce nœud. En outre, le nœud porte des informations sur la météo ou non il a été « échangé », à savoir si elle a vu toutes les permutations possibles de c'est sous-arbre. L'arbre est centré de gauche, ce qui signifie que le noeud droit doit toujours (sauf dans certains cas, que je ne ai pas besoin pour couvrir cet algorithme) soit un nœud feuille, tandis que le noeud gauche est toujours soit une feuille ou une branche.

L'algorithme J'utilise au moment peut être décrit un peu comme ceci:

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'

serait quelque chose comme le comportement souhaité du Algoritm ceci:

            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  

et ainsi de suite ...

Answer 1

La structure est juste complètement inadapté pour les permutations, mais comme vous le savez vous est centré à gauche pourrait être en mesure de faire quelques hypothèses que vous aider.

Je l'ai essayé de travailler d'une manière similaire à la vôtre, et je toujours suis pris sur le fait que vous avez seulement une information binaire (permutés ou non) qui ne suffit pas. Pour quatre feuilles, vous avez 4! (24) combinaisons possibles, mais vous n'avez vraiment trois branches (3 bits, 8 combinaisons possibles) pour stocker les informations d'état permuté. Vous n'avez tout simplement pas un endroit pour stocker ces informations.

Mais peut-être que vous pourriez écrire un transbordeur qui passe par l'arbre et utilise le nombre de feuilles pour déterminer combien de swaps sont nécessaires, puis passe par ces swaps systématiquement au lieu de simplement laisser à l'arbre lui-même.

Quelque chose comme

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

Cela pourrait ne pas convenir à votre application, mais vous n'avez pas donné que beaucoup de détails sur la raison pour laquelle vous avez besoin de le faire la façon dont vous le faites. La façon dont vous faites maintenant ne fonctionnera pas, puisque factoriel (le nombre de permutations) croît plus vite que exponentielle (le nombre de bits que vous avez « troqué »). Si vous aviez 8 feuilles, vous auriez 7 branches et 8 feuilles pour un total de 15 bits. Il y a 40320 permutation de 8 feuilles, et seulement 32768 combinaisons possibles de 15 bits. Mathématiquement, vous ne pouvez pas représenter les permutations.

Answer 2

Quel est le problème de faire une liste de tous les éléments de l'arborescence, utilisez des moyens génératives pour construire toutes les commandes possibles (voir Knuth Vol 4), puis les re-map à la structure de l'arbre?