检索树结构所有排列的有效方法

Question

编辑更大的树，以获得更多示例。

我有一个树结构，需要生成所有可能的排列，但有一些限制。给定一个像这样的树：

    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)之一和(C1)之一。因此，从 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 有两个桶，一个包含“B”，另一个包含“C”。如果这就是它的全部（并且 C 下面没有存储桶），我将拥有“A1 B1 C1”和“A1 B2 C1”——所有子存储桶中至少有一个代表。

所以我认为每个桶都需要其子桶的叉积（一直向下）。

Answer 1

使用以下子命令：

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 ，但这会严重混淆任何维护代码的人，因为 path 具有易于理解的含义。你可以通过一点聪明来完全回避命名问题：

print join "\n" =>
      map { join "" => map "@$_\n", @$_ }
      map [ enumerate($_) ] => @$nodes;

Answer 2

每个节点都应该知道其父节点 (GetParentRow)，以便您可以将父节点作为参数传递给递归方法。这样，当您到达“叶子”时，您可以递归地追溯到根。

我不确定这是否是最有效的方法，但我认为它应该给你你想要的结果。

Answer 3

树行走可以按任何所需的顺序执行，如下所示。对于根节点，将所有子节点放入 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; } }
}

那么我们所要做的就是走这条路。与此类似的东西应该可以解决问题：

[删除了不正确的解决方案]

再次编辑：

好的，我终于弄清楚了你想要什么。在沿着树向下移动之前，您希望水平移动每条路径中不同“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);
        }
    }


}

Answer 4

首先我以为你想要所有的生成树。 http://en.wikipedia.org/wiki/Spanning_tree

但后来我意识到你想要什么有点像从树根开始的“跨越步行”。

然后我意识到这（相对）简单。

Foreach leaf

Walk from the leaf to the root

end for

当然，你需要一个真正的数据结构，我不认为 Perl 的哈希哈希有效；每个节点中都需要一个“父”指针。