c# - 树组合和分区

Question

我有一个(非二进制)树，其中包含带字符串的记录。

我想按如下方式制作包含数据的记录数组(或指向记录的指针)...

我制作了这个插图示例:

       ABCDEFGHIJKL
      /     |      \
   ABC      DE      FGHIJKL
  /   \            /   |   \
AB     C        FGH   IJK   L
                      / \
                     I  JK

结果应该是:
(7 个数组包含具有此数据的记录)

1. ABCDEFGHIJKL
2. ABC、DE、FGHIJKL
3. ABC、DE、FGH、I、JK、L
4. ABC、DE、FGH、IJK、L
5. AB、C、DE、FGHIJKL
6. AB、C、DE、FGH、I、JK、L
7. AB、C、DE、FGH、IJK、L

一些注意事项:

• 我不关心第 (1-7) 个结果的顺序，只要我得到它们即可。
• 我正在使用 C#
• 在此示例中有 4 个级别和 7 条路径，但在现实生活中它可以是任意数量的级别。
• 此处的模式是根据我从左到右的所有组合创建"ABCDEFGHIJKL"。

有人有什么建议吗？

Answer 1

这个想法很简单。有一个只有根节点的列表，然后用它的子节点替换它。然后递归地替换该列表中的每个节点，并在每次替换操作时将该列表添加到结果集合中。

这样我们会在一些分支中得到重复的结果，所以我们将通过递归传递结果集合并检查当前节点列表是否已经存在。如果是，那么它的派生列表也是如此，所以只返回。

假设我们有一个 Tree 类，其中包含 Node 类的节点(每个节点都有 Children)。树根是 Root。然后你可以像这样实现你的功能(在 Tree 类中):

public List<List<Node>> GetLevels() {
    List<Node> nodes = new List<Node>();
    nodes.Add(Root);
    List<List<Node>> result = new List<List<Node>>();
    GetLevelsCore(nodes, result);
    return result;
}
void GetLevelsCore(List<Node> nodes, List<List<Node>> result) {
    if(result.Any(list => list.SequenceEqual(nodes))) return;
    result.Add(nodes);

    foreach(Node node in nodes) {
        if(node.Children.Count != 0) {
            List<Node> replacedNodes = new List<Node>(nodes);
            int index = replacedNodes.IndexOf(node);
            replacedNodes.RemoveAt(index);
            replacedNodes.InsertRange(index, node.Children);

            GetLevelsCore(replacedNodes, result);
        }
    }
}

我得到的结果:

List<List<Node>> result = tree.GetLevels();
List<string> strings = new List<string>(result.Select(nodes => string.Join(", ", nodes.Select(node => node.Value))));

字符串:

1. “ABCDEFGHIJKL”
2. “ABC、DE、FGHIJKL”
3. “AB、C、DE、FGHIJKL”
4. “AB、C、DE、FGH、IJK、L”
5. “AB、C、DE、FGH、I、JK、L”
6. “ABC、DE、FGH、IJK、L”
7. “ABC、DE、FGH、I、JK、L”

UPD:用 Any() 替换了 Contains 检查，现在不需要相等比较器。