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

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 возможных комбинаций) для хранения замененной информации о состоянии.Вам просто негде хранить эту информацию.

Но, возможно, вы могли бы написать обходчик, который проходит через дерево и использует количество листьев, чтобы определить, сколько свопов необходимо, а затем систематически проходит через эти свопы, вместо того, чтобы просто оставлять это на усмотрение самого дерева.

Что-то вроде

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