4

より多くの例のために、より大きなツリー用に編集されました。

いくつかの制限付きで、考えられるすべての順列を生成する必要があるツリー構造があります。次のようなツリーがあるとします。

    A1----(B1, B2)
     \    
      \___(C1)
             \__(E1, E2)
/       
-  A2----(B3, B4)
\     \     \
       \     \__(D1)
        \
         \_(F1, F2)
                |
                (D4)   

    A3----(B5, B6)
                \__(D2, D3)

または、これが少し漠然としている場合は、Perl 表記で行われた同じ構造を次に示します。

my $nodes = [
{
    name => 'A1',
    children => [
        [ { name => 'B1', children => []  }, 
          { name => 'B2', children => []  }
        ],
        [
          { name => 'C1', 
                    children => [
                        [
                            { name => 'E1', children => [] },
                            { name => 'E2', children => [] }
                        ]
                    ]
            }
        ]
    ]
},
{
    name => 'A2',
    children => [
        [ { name => 'B3', 
                children => [
                    [
                        { name => 'D1', children => [] }
                    ]
                ] 
          },
          { name => 'B4', children => [] }
        ],
        [
          { name => 'F1', children => [] },
          { name => 'F2', children => [
                        [ { name => 'D4', children => [] } ]
                    ]
            }
        ]
    ]
},
{
    name => 'A3',
    children => [
        [ { name => 'B5', children => [] },
          { name => 'B6', children => [
                    [ { name => 'D2', children => [] },
                      { name => 'D3', children => [] }
                    ] 
                ]                 
            }
        ]
    ]
}

];

(率直に言って、これを読み取り可能なPerl で理解できるなら、私もそれを採用します。)

ツリーをトラバースして、可能な「パス」をすべて最上位から下に取得しようとしています。ノードのすべての子孫グループは、「パス」内の正確に 1 つのメンバーによって表される必要があります。たとえば、A1 では、(B1、B2) の 1 つと (C1) の 1 つを表す必要があります。したがって、A1 から下る各パスは次のいずれかで始まります。

A1 B1 C1

また

A1 B2 C1

B1、B2、または C1 に子がある場合は、それらも表す必要があります。

上記のツリーに対してこれを手作業で処理すると、次の可能性が得られます。

A1 B1 C1 E1
A1 B1 C1 E2
A1 B2 C1 E1
A1 B2 C1 E2

A2 B3 D1 F1
A2 B3 D1 F2 D4
A2 B4 F1
A2 B4 F2 D4

A3 B5
A3 B6 D2
A3 B6 D3

ここの各ノードは DataRow オブジェクトです。

internal class DataRow
{
    internal string tag = "";
    internal int id = 0;
    internal Dictionary<string, List<DataRow>> children = null;

    internal DataRow(int id, string tagname)
    {
        this.tag = tagname;
        this.id = id;
    }        internal void AddChildren(string type, List<DataRow> drList)
    {
        if (children == null)
            children = new Dictionary<string, List<DataRow>>();
        if (!children.ContainsKey(type))
            children[type] = new List<DataRow>();
        children[type].AddRange(drList);
    }
    internal void AddChild(string type, DataRow dr)
    {
        List<DataRow> drList = new List<DataRow>();
        drList.Add(dr);
        AddChildren(type, drList);
    }
    public override string ToString()
    {
        return this.tag + " " + this.id;
    }
}

上記のサンプル ツリーを構築するには (後で追加される E および F レベルを除く):

        DataRow fullList = new DataRow(null, "");
        DataRow dr, dr2, dr3;

        // First node above
        dr = new DataRow(1, "A");
        List<DataRow> drList = new List<DataRow>();
        drList.Add(new DataRow(1, "B"));
        drList.Add(new DataRow(2, "B"));
        dr.AddChildren("B", drList);
        drList.Clear();
        dr2 = new DataRow(1, "C");
        dr2.AddChild("C", new DataRow(1, "E"));
        dr2.AddChild("C", new DataRow(2, "E"));
        drList.Add(dr2);
        dr.AddChildren("C", drList);
        fullList.AddChild("A", dr);


        // Second Node above (without the "F" stuff)
        drList.Clear();
        dr = new DataRow(3, "B");
        dr.AddChild("D", new DataRow(1, "D"));
        drList.Add(dr);
        drList.Add(new DataRow(4, "B"));
        dr = new DataRow(2, "A");
        dr.AddChildren("B", drList);
        fullList.AddChild("A", dr);

        // Third node above
        drList.Clear();
        dr3 = new DataRow(6, "B");
        dr3.AddChild("B", new DataRow(2, "D"));
        dr3.AddChild("B", new DataRow(3, "D"));
        dr2 = new DataRow(3, "A");
        dr2.AddChild("B", new DataRow(5, "B"));
        dr2.AddChild("B", dr3);
        fullList.AddChild("A", dr2);

ツリー全体を歩くのは簡単です:

    internal void PermutedList()
    {
        if ( children == null ) return;
        foreach (string kidType in children.Keys)
        {
            foreach (DataRow dr in children[kidType])
            {
                dr.PermutedList();
            }
        }
    }

しかし、それは私が必要とするものではありません。この問題は完全なツリー ウォークですが、特定の順序です。何が得られないのですか？これはどんな散歩ですか？

私は 10 年前に Perl で書いたこれの面倒で遅い実装を持っていますが、もう自分のコードを解読することはできません (恥を知れ!)。

編集:グラフと以下のリストは展開されていますが、コードは展開されていません。

グラフを説明できれば、プログラムできます。それが何と呼ばれているか知っていれば、それを調べることができた。しかし、私はできません。ということで、もう少し詳しく説明します。

バケット名は重要ではありません!

各ノードには「子のバケット」があります。A1 には 2 つのバケットがあり、1 つは「B」を含み、もう 1 つは「C」を含みます。それだけの場合 (そして C の下にバケットがなかった場合)、「A1 B1 C1」と「A1 B2 C1」が存在することになります。これは、存在するすべての子バケットから少なくとも 1 つの代表です。

したがって、各バケットには、その子の外積が必要だと思います (ずっと下まで)。

4

4 に答える 4

3

次のサブを使用します。

use 5.10.0;  # for // (aka defined-or)

use subs 'enumerate';
sub enumerate {
  my($root) = @_;

  my $kids = $root->{children};
  return [ $root->{name} // () ]
    unless @$kids;

  my @results;
  foreach my $node (@{ $kids->[0] }) {
    my @fronts = map [ $root->{name} // (), @$_ ],
                     enumerate $node;

    my @below = enumerate {
      name => undef,
      children => [ @{$kids}[1 .. $#$kids ] ],
    };

    foreach my $a (@fronts) {
      foreach my $b (@below) {
        push @results => [ @$a, @$b ];
      }
    }
  }

  @results;
}

あなたはそれを印刷するかもしれません

foreach my $tree (@$nodes) {
  foreach my $path (enumerate $tree) {
    print "@$path\n";
  }

  print "\n";
}

次の出力を取得するには：

A1 B1 C1 E1
A1 B1 C1 E2
A1 B2 C1 E1
A1 B2 C1 E2

A2 B3 D1 F1
A2 B3 D1 F2 D4
A2 B4 F1
A2 B4 F2 D4

A3 B5
A3 B6 D2
A3 B6 D3

上記で使用$pathしましたが、パスにはよく理解されている意味があるため、コードを管理している人は誰でも深刻に混乱します。少し賢くして、名前の問題を完全に回避することができます。

print join "\n" =>
      map { join "" => map "@$_\n", @$_ }
      map [ enumerate($_) ] => @$nodes;
于 2010-01-22T17:48:12.457 に答える
1

ツリーウォークは、次のように任意の順序で実行できます。ルートノードの場合、すべての子をDATA_STRUCTUREに配置します（以下で説明します）。次に、DATA_STRUCTUREからノードを取り出し、そのすべての子をDATA_STRUCTUREに配置します。DATA_STRUCTUREが空になるまで続行します。

秘訣は、適切なDATA_STRUCTUREを選択することです。順序どおりの（深さ優先）トラバーサルの場合、スタックを使用できます。（子は逆の順序でスタックにプッシュされる必要があります。）深さ優先トラバーサルを実行するには、キューを使用できます。

より複雑な注文の場合、優先キューがチケットです。使用している基準に基づいて、ツリーをトラバースする順序に従って優先順位を設定するだけです。実際、優先順位を正しく設定すると、スタックまたはキューとしても動作し、前述の深さ優先シーケンスと幅優先シーケンスがそれぞれ発生します。

追加するために編集：

ツリーウォーキングアルゴリズムは、サイクルがないため、このタイプのデータ構造に対しては問題なく機能します。セット内の各アイテムのデータ構造に新しいノードを配置するだけです。余分なのは、パスを表す方法だけだと思います。

パスは非常に簡単です。次のようなものが必要です。

class Path<T>
{
    T lastNode;
    Path<T> previousNodes;
    public Path(T lastNode, Path<T> previousNodes)
    {
        this.lastNode = lastNode; this.previousNodes = previousNodes;
    }
    public IEnumerable<T> AllNodes()
    {
        return AllNodesBackwards().Reverse();
    }
    private IEnumerable<T> AllNodesBackwards()
    {
        Path<T> currentPath = this;
        while (currentPath != null)
        {
            yield return currentPath.lastNode;
            currentPath = currentPath.previousNodes;
        }
    }
    public T Node { get { return lastNode; } }
}

だから私たちがしなければならないのは道を歩くことだけです。これに似た何かがトリックを行う必要があります：

[間違ったソリューションが削除されました]

再度編集：

OK、私はついにあなたが欲しいものを見つけました。ツリーを下る前に、各パスで異なる「kidTypes」の子を水平方向に移動する必要があります。

それは大きな混乱ですが、私はそれを解決しました：

public void WalkPath2()
{
    Queue<Path<DataRow>> queue = new Queue<Path<DataRow>>();
    queue.Enqueue(new Path<DataRow>(this, null));

    while (queue.Count > 0)
    {
        Path<DataRow> currentPath = queue.Dequeue();
        DataRow currentNode = currentPath.Node;

        if (currentNode.children != null)
        {
            foreach (Path<DataRow> nextPath in currentNode.GetChildPermutations(currentPath))
                queue.Enqueue(nextPath);
        }
        else
        {
            foreach (DataRow node in currentPath.AllNodes())
            {
                Console.Write(node.ToString());
                Console.Write("      ");
            }
            Console.WriteLine();
        }

    }

}

private IEnumerable<Path<DataRow>> GetChildPermutations(Path<DataRow> currentPath)
{
    string firstLevelKidType = null;
    foreach (string kidType in children.Keys)
    {
        firstLevelKidType = kidType;
        break;
    }
    foreach (Path<DataRow> pathPermutation in GetNextLevelPermutations(currentPath, firstLevelKidType))
        yield return pathPermutation;
}

private IEnumerable<Path<DataRow>> GetNextLevelPermutations(Path<DataRow> currentPath, string thisLevelKidType)
{
    string nextLevelKidType = null;
    bool nextKidTypeIsTheOne = false;
    foreach (string kidType in children.Keys)
    {
        if (kidType == thisLevelKidType)
            nextKidTypeIsTheOne = true;
        else
        {
            if (nextKidTypeIsTheOne)
            {
                nextLevelKidType = kidType;
                break;
            }
        }
    }

    foreach (DataRow node in children[thisLevelKidType])
    {
        Path<DataRow> nextLevelPath = new Path<DataRow>(node, currentPath);
        if (nextLevelKidType != null)
        {
            foreach (Path<DataRow> pathPermutation in GetNextLevelPermutations(nextLevelPath, nextLevelKidType))
                yield return pathPermutation;
        }
        else
        {
            yield return new Path<DataRow>(node, currentPath);
        }
    }


}
于 2010-01-21T19:44:13.497 に答える
1

各ノードはその親 (GetParentRow) を知っている必要があるため、親を引数として再帰メソッドに渡すことができます。このようにして、「リーフ」に到達すると、再帰的にルートに戻ることができます。

それが最も効率的な方法かどうかはわかりませんが、必要な結果が得られるはずです。

于 2010-01-20T16:49:32.150 に答える
0

最初に、すべてのスパニング ツリーが必要だと思いました。http://en.wikipedia.org/wiki/Spanning_tree

しかしその後、あなたが求めていたのは、木の根元からの「スパンニング ウォーク」のようなものであることに気付きました。

それから私はそれが（比較的）単純であることに気付きました。

Foreach leaf

Walk from the leaf to the root

end for

もちろん、真のデータ構造が必要になります。Perl のハッシュのハッシュは機能しないと思います。各ノードに「親」ポインターが必要です。

于 2010-01-21T19:33:35.387 に答える