Permuting شجرة ثنائية دون استخدام القوائم

Question

ولست بحاجة لايجاد خوارزمية لتوليد كل التقليب ممكن من شجرة ثنائية، وبحاجة للقيام بذلك دون استخدام القوائم (وذلك لأن الشجرة نفسها تحمل دلالات والقيود التي لا يمكن ترجمتها إلى قوائم). لقد وجدت خوارزمية التي تعمل من أجل الأشجار مع ارتفاع ثلاثة أو أقل، ولكن كلما أحصل على مستويات أعلى، وتفقد مجموعة واحدة من التبديلات الممكنة في ارتفاع بإضافة.

وكل عقدة تحمل معلومات عن حالته الأصلية، بحيث عقدة واحدة يمكن تحديد ما إذا كان قد حوكموا جميع التبديلات الممكنة لهذه العقدة. أيضا، عقدة يحمل معلومات عن الطقس أو لا انه تم "تبادلت"، أي إذا كان قد رأيت كل التباديل الممكنة لانها الشجرة الفرعية. ويترك التي تركز على الشجرة، وهذا يعني أن العقدة الصحيحة ينبغي دائما (ما عدا في بعض الحالات التي لا تحتاج لتغطية هذه الخوارزمية) تكون عقدة ورقة، في حين أن عقدة اليسرى دائما إما ورقة أو فرع.

والخوارزمية أنا باستخدام في الوقت الراهن يمكن وصف نوع من مثل هذا:

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'

وقال إن السلوك المطلوب من خوارزمية يكون شيئا مثل هذا:

            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  

ووهلم جرا ...

Answer 1

وهيكل هو فقط غير ملائم تماما لالتباديل، ولكن منذ ان تعرفه تبقى محورها كنت قد تكون قادرة على تقديم بعض الافتراضات التي تساعدك على الخروج.

وحاولت العمل بطريقة مماثلة ليدكم، وأنا دائما حصلت واقعة على حقيقة أن لديك سوى قطعة ثنائي المعلومات (تبادلت أو لا) وهي ليست كافية. لمدة أربعة أوراق، لديك 4! (24) التوليفات الممكنة، لكنك لا تملك إلا حقا ثلاثة فروع (3 بت و 8 التركيبات الممكنة) لتخزين معلومات حالة تبادلت. كنت ببساطة لم يكن لديك مكان لتخزين هذه المعلومات.

ولكن ربما يمكن أن تكتب traverser أن يذهب من خلال الشجرة ويستخدم عدد من الأوراق لتحديد عدد مقايضة المطلوبة، وبعد ذلك يذهب من خلال تلك المقايضات منهجي بدلا من مجرد تركها إلى الشجرة نفسها.

وشيء من هذا القبيل

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

وهذا قد لا يكون مناسبا للتطبيق الخاص بك، ولكنك لم بالنظر إلى أن الكثير من التفاصيل حول لماذا تحتاج للقيام بذلك الطريق كنت أفعل ذلك. الطريق كنت أفعل ذلك الآن ببساطة لن ينجح، لأن مضروب (عدد التباديل) تنمو أسرع من الأسي (عدد البتات "مبادلة" لديك). إذا كان لديك 8 أوراق، سيكون لديك 7 فروع و 8 أوراق ليصبح المجموع 15 بت. هناك 40320 التقليب من 8 أوراق، وفقط 32768 التوليفات الممكنة من 15 بت. رياضيا، كنت ببساطة لا يمكن أن تمثل التباديل.

Answer 2

ما هو الخطأ في وضع قائمة من كافة العناصر الموجودة في شجرة، استخدام وسائل توليدي لبناء جميع الطلبات الممكنة (انظر كانوث المجلد 4)، ومن ثم إعادة رسم خريطة لها هيكل الشجرة؟