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

为更大的树编辑,以获取更多示例。

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

    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 => [] }
                    ] 
                ]                 
            }
        ]
    ]
}

];

(坦率地说,如果你能在 可读性 帕尔,我也要这个。)

我正在寻找穿过这棵树并从顶层向下检索所有可能的“路径”。节点的所有后代组必须由“路径”中的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

这里的每个节点都是一个数据行对象:

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”——至少一个来自所有子桶的代表。

所以我认为每个桶都需要它的子代的叉积(一直向下)。