リストを使わないバイナリツリーのパーミッション

Question

バイナリツリーのすべての可能な順列を生成するためのアルゴリズムを見つけ出す必要があります。リストを使わずにそれを行う必要があります（これは、ツリー自体が持つことができないセマンティクスとリストに変換されます）。私は木の高さが3以下のアルゴリズムには適していますが、高さが高くなるたびに高さごとに1組の可能な並べ替えが緩和されます。

各ノードは元の状態に関する情報を保持しているため、あるノードがそのノードに対して可能なすべての順列が試行されたかどうかを判断できます。また、ノードは天気に関する情報を運ぶか、「スワップ」されていない、すなわち、それが可能なすべてのパーツの部分木を見た場合には、情報を運ぶ。ツリーは左にセンタリングされています。つまり、右のノードは常に（このアルゴリズムをカバーする必要がない場合を除いて）リーフノードでなければならず、左のノードは常にリーフまたはブランチです。

私は、現時点で使用しているアルゴリズムは、ソートのこのように記述することができますように

  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 

と：そのアルゴリズムの所望の動作はこのようなものになるだろう

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' 

...

Answer 1

この構造はまったく順列には適していませんが、左寄せであることを知っているので、あなたを助けるいくつかの前提ができます。

私はあなたと似たような仕組みで作業しましたが、バイナリ情報（スワップされているかどうか）だけでは不十分です。 4枚の葉には、4枚あります！ （24）の可能な組み合わせがありますが、スワップされた状態情報を格納するために実際には3つのブランチ（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枚の葉を持っていたら、合計15ビットの7つの枝と8つの葉があります。 8枚の葉の40320の置換があり、15ビットの可能な組み合わせは32768通りしかありません。数学的には、単に置換を表すことはできません。

Answer 2

ツリー内のすべてのアイテムのリストを作成するのに間違ったことは、すべての可能な注文を作成するための生成手段を使用します（Knuth 4巻を参照）。