Перестановка двоичного дерева без использования списков

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), а затем повторно сопоставить их с древовидной структурой?