2

二分木の可能なすべての順列を生成するためのアルゴリズムを見つける必要があり、リストを使用せずにそれを行う必要があります（これは、ツリー自体がリストに変換できないセマンティクスと制約を持っているためです）。高さが3以下の木で機能するアルゴリズムを見つけましたが、高さが高くなると、追加された高さごとに1セットの可能な順列が失われます。

各ノードは元の状態に関する情報を保持しているため、1つのノードは、そのノードに対してすべての可能な順列が試行されたかどうかを判断できます。また、ノードは天気に関する情報を保持しているか、「スワップ」されているかどうか、つまり、サブツリーのすべての可能な順列を確認したかどうかを確認します。ツリーは左中央にあります。つまり、右側のノードは常にリーフノードである必要がありますが（このアルゴリズムでカバーする必要がない場合を除く）、左側のノードは常にリーフまたはブランチのいずれかです。

私が現在使用しているアルゴリズムは、次のように説明できます。

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

等々...

4

2 に答える 2

3

構造は順列にはまったく適していませんが、左中央に配置されていることがわかっているため、役立ついくつかの仮定を立てることができる場合があります。

私はあなたと同様の方法でそれを操作しようとしましたが、十分ではないバイナリ情報 (スワップされているかどうかにかかわらず) しか持っていないという事実に常に気付きました。葉が 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 つある場合、7 つのブランチと 8 つのリーフがあり、合計 15 ビットになります。8 つの葉の 40320 の順列と、15 ビットの可能な組み合わせは 32768 のみです。数学的には、単純に順列を表すことはできません。

于 2009-03-26T13:42:25.177 に答える
0

ツリー内のすべてのアイテムのリストを作成し、生成手段を使用してすべての可能な順序を構築し (Knuth Vol 4 を参照)、それらをツリー構造に再マッピングすることの何が問題になっていますか?

于 2009-03-26T13:34:35.460 に答える