C# 递归列表展平

Recursive List Flattening

提问by Matt H

I could probably write this myself, but the specific way I'm trying to accomplish it is throwing me off. I'm trying to write a generic extension method similar to the others introduced in .NET 3.5 that will take a nested IEnumerable of IEnumerables (and so on) and flatten it into one IEnumerable. Anyone have any ideas?

我可能自己写这个，但我试图完成它的具体方式让我失望。我正在尝试编写一个类似于 .NET 3.5 中引入的其他方法的通用扩展方法，它将采用 IEnumerables 的嵌套 IEnumerable（等等）并将其展平为一个 IEnumerable。谁有想法？

Specifically, I'm having trouble with the syntax of the extension method itself so that I can work on a flattening algorithm.

具体来说，我在扩展方法本身的语法方面遇到了问题，因此我可以使用展平算法。

采纳答案by Jon Skeet

Hmm... I'm not sure exactlywhat you want here, but here's a "one level" option:

嗯......我不确定你到底想要什么，但这里有一个“一级”选项：

public static IEnumerable<TElement> Flatten<TElement,TSequence> (this IEnumerable<TSequence> sequences)
    where TSequence : IEnumerable<TElement> 
{
    foreach (TSequence sequence in sequences)
    {
        foreach(TElement element in sequence)
        {
            yield return element;
        }
    }
}

If that's not what you want, could you provide the signature of what you do want? If you don't need a generic form, and you just want to do the kind of thing that LINQ to XML constructors do, that's reasonably simple - although the recursive use of iterator blocks is relatively inefficient. Something like:

如果这不是你想要的，你能提供你想要的签名吗？如果您不需要通用表单，而只想做 LINQ to XML 构造函数所做的事情，那相当简单——尽管迭代器块的递归使用效率相对较低。就像是：

static IEnumerable Flatten(params object[] objects)
{
    // Can't easily get varargs behaviour with IEnumerable
    return Flatten((IEnumerable) objects);
}

static IEnumerable Flatten(IEnumerable enumerable)
{
    foreach (object element in enumerable)
    {
        IEnumerable candidate = element as IEnumerable;
        if (candidate != null)
        {
            foreach (object nested in candidate)
            {
                yield return nested;
            }
        }
        else
        {
            yield return element;
        }
    }
}

Note that that will treat a string as a sequence of chars, however - you may want to special-case strings to be individual elements instead of flattening them, depending on your use case.

请注意，这会将字符串视为字符序列 - 您可能希望将特殊情况字符串作为单个元素而不是将它们展平，具体取决于您的用例。

Does that help?

这有帮助吗？

回答by Torbj?rn Gyllebring

static class EnumerableExtensions
{
    public static IEnumerable<T> Flatten<T>(this IEnumerable<IEnumerable<T>> sequence)
    {
        foreach(var child in sequence)
            foreach(var item in child)
                yield return item;
    }
}

Maybe like this? Or do you mean that it could potentially be infintly deep?

也许像这样？或者你的意思是它可能会无限深？

回答by FlySwat

Basicly, you need to have a master IENumerable that is outside of your recursive function, then in your recursive function (Psuedo-code)

基本上，你需要有一个主IENumerable，它在你的递归函数之外，然后在你的递归函数中（伪代码）

private void flattenList(IEnumerable<T> list)
{
    foreach (T item in list)
    {
        masterList.Add(item);

        if (item.Count > 0)
        {
            this.flattenList(item);
        }
    }
}

Though I'm really not sure what you mean by IEnumerable nested in an IEnumerable...whats within that? How many levels of nesting? Whats the final type? obviously my code isn't correct, but I hope it gets you thinking.

虽然我真的不确定你所说的嵌套在 IEnumerable 中的 IEnumerable 是什么意思......里面有什么？嵌套多少级？最后的类型是什么？显然我的代码不正确，但我希望它能让你思考。

回答by Mark Brackett

Isn't that what [SelectMany][1] is for?

这不是 [SelectMany][1] 的用途吗？

enum1.SelectMany(
    a => a.SelectMany(
        b => b.SelectMany(
            c => c.Select(
                d => d.Name
            )
        )
    )
);

回答by Mark Brackett

Here's an extension that might help. It will traverse all nodes in your hierarchy of objects and pick out the ones that match a criteria. It assumes that each object in your hierarchy has a collection propertythat holds its child objects.

这是一个可能有帮助的扩展。它将遍历对象层次结构中的所有节点，并挑选出符合条件的节点。它假定层次结构中的每个对象都有一个集合属性来保存其子对象。

Here's the extension:

这是扩展名：

/// Traverses an object hierarchy and return a flattened list of elements
/// based on a predicate.
/// 
/// TSource: The type of object in your collection.</typeparam>
/// source: The collection of your topmost TSource objects.</param>
/// selectorFunction: A predicate for choosing the objects you want.
/// getChildrenFunction: A function that fetches the child collection from an object.
/// returns: A flattened list of objects which meet the criteria in selectorFunction.
public static IEnumerable<TSource> Map<TSource>(
  this IEnumerable<TSource> source,
  Func<TSource, bool> selectorFunction,
  Func<TSource, IEnumerable<TSource>> getChildrenFunction)
{
  // Add what we have to the stack
  var flattenedList = source.Where(selectorFunction);

  // Go through the input enumerable looking for children,
  // and add those if we have them
  foreach (TSource element in source)
  {
    flattenedList = flattenedList.Concat(
      getChildrenFunction(element).Map(selectorFunction,
                                       getChildrenFunction)
    );
  }
  return flattenedList;
}

Examples (Unit Tests):

示例（单元测试）：

First we need an object and a nested object hierarchy.

首先我们需要一个对象和一个嵌套的对象层次结构。

A simple node class

一个简单的节点类

class Node
{
  public int NodeId { get; set; }
  public int LevelId { get; set; }
  public IEnumerable<Node> Children { get; set; }

  public override string ToString()
  {
    return String.Format("Node {0}, Level {1}", this.NodeId, this.LevelId);
  }
}

And a method to get a 3-level deep hierarchy of nodes

以及一种获得 3 级深度节点层次结构的方法

private IEnumerable<Node> GetNodes()
{
  // Create a 3-level deep hierarchy of nodes
  Node[] nodes = new Node[]
    {
      new Node 
      { 
        NodeId = 1, 
        LevelId = 1, 
        Children = new Node[]
        {
          new Node { NodeId = 2, LevelId = 2, Children = new Node[] {} },
          new Node
          {
            NodeId = 3,
            LevelId = 2,
            Children = new Node[]
            {
              new Node { NodeId = 4, LevelId = 3, Children = new Node[] {} },
              new Node { NodeId = 5, LevelId = 3, Children = new Node[] {} }
            }
          }
        }
      },
      new Node { NodeId = 6, LevelId = 1, Children = new Node[] {} }
    };
  return nodes;
}

First Test: flatten the hierarchy, no filtering

第一个测试：扁平化层次结构，没有过滤

[Test]
public void Flatten_Nested_Heirachy()
{
  IEnumerable<Node> nodes = GetNodes();
  var flattenedNodes = nodes.Map(
    p => true, 
    (Node n) => { return n.Children; }
  );
  foreach (Node flatNode in flattenedNodes)
  {
    Console.WriteLine(flatNode.ToString());
  }

  // Make sure we only end up with 6 nodes
  Assert.AreEqual(6, flattenedNodes.Count());
}

This will show:

这将显示：

Node 1, Level 1
Node 6, Level 1
Node 2, Level 2
Node 3, Level 2
Node 4, Level 3
Node 5, Level 3

Second Test: Get a list of nodes that have an even-numbered NodeId

第二个测试：获取具有偶数 NodeId 的节点列表

[Test]
public void Only_Return_Nodes_With_Even_Numbered_Node_IDs()
{
  IEnumerable<Node> nodes = GetNodes();
  var flattenedNodes = nodes.Map(
    p => (p.NodeId % 2) == 0, 
    (Node n) => { return n.Children; }
  );
  foreach (Node flatNode in flattenedNodes)
  {
    Console.WriteLine(flatNode.ToString());
  }
  // Make sure we only end up with 3 nodes
  Assert.AreEqual(3, flattenedNodes.Count());
}

This will show:

这将显示：

Node 6, Level 1
Node 2, Level 2
Node 4, Level 3

回答by leppie

The SelectManyextension method does this already.

该SelectMany扩展方法已经做了这个。

Projects each element of a sequence to an IEnumerable<(Of <(T>)>) and flattens the resulting sequences into one sequence.

将序列的每个元素投影到 IEnumerable<(Of <(T>)>) 并将结果序列展平为一个序列。

回答by jfs

Here is a modified Jon Skeet's answerto allow more than "one level":

这是修改过的Jon Skeet 的答案，允许超过“一个级别”：

static IEnumerable Flatten(IEnumerable enumerable)
{
    foreach (object element in enumerable)
    {
        IEnumerable candidate = element as IEnumerable;
        if (candidate != null)
        {
            foreach (object nested in Flatten(candidate))
            {
                yield return nested;
            }
        }
        else
        {
            yield return element;
        }
    }
}

disclaimer: I don't know C#.

免责声明：我不知道 C#。

The same in Python:

在 Python 中也是如此：

#!/usr/bin/env python

def flatten(iterable):
    for item in iterable:
        if hasattr(item, '__iter__'):
            for nested in flatten(item):
                yield nested
        else:
            yield item

if __name__ == '__main__':
    for item in flatten([1,[2, 3, [[4], 5]], 6, [[[7]]], [8]]):
        print(item, end=" ")

It prints:

它打印：

1 2 3 4 5 6 7 8 

回答by Richard Collette

Since yield is not available in VB and LINQ provides both deferred execution and a concise syntax, you can also use.

由于 VB 中没有 yield 并且 LINQ 提供延迟执行和简洁的语法，因此您也可以使用。

<Extension()>
Public Function Flatten(Of T)(ByVal objects As Generic.IEnumerable(Of T), ByVal selector As Func(Of T, Generic.IEnumerable(Of T))) As Generic.IEnumerable(Of T)
    Return objects.Union(objects.SelectMany(selector).Flatten(selector))
End Function

回答by marchewek

I thought I'd share a complete example with error handling and a single-logic apporoach.

我想我会分享一个包含错误处理和单一逻辑方法的完整示例。

Recursive flattening is as simple as:

递归展平非常简单：

LINQ version

LINQ版本

public static class IEnumerableExtensions
{
    public static IEnumerable<T> SelectManyRecursive<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> selector)
    {
        if (source == null) throw new ArgumentNullException("source");
        if (selector == null) throw new ArgumentNullException("selector");

        return !source.Any() ? source :
            source.Concat(
                source
                .SelectMany(i => selector(i).EmptyIfNull())
                .SelectManyRecursive(selector)
            );
    }

    public static IEnumerable<T> EmptyIfNull<T>(this IEnumerable<T> source)
    {
        return source ?? Enumerable.Empty<T>();
    }
}

Non-LINQ version

非 LINQ 版本

public static class IEnumerableExtensions
{
    public static IEnumerable<T> SelectManyRecursive<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> selector)
    {
        if (source == null) throw new ArgumentNullException("source");
        if (selector == null) throw new ArgumentNullException("selector");

        foreach (T item in source)
        {
            yield return item;

            var children = selector(item);
            if (children == null)
                continue;

            foreach (T descendant in children.SelectManyRecursive(selector))
            {
                yield return descendant;
            }
        }
    }
}

Design decisions

设计决策

I decided to:

我决定：

• disallow flattening of a null IEnumerable, this can be changed by removing exception throwing and:
  • adding source = source.EmptyIfNull();before returnin the 1st version
  • adding if (source != null)before foreachin the 2nd version
• allow returning of a null collection by the selector - this way I'm removing responsibility from the caller to assure the children list isn't empty, this can be changed by:
  • removing .EmptyIfNull()in the first version - note that SelectManywill fail if null is returned by selector
  • removing if (children == null) continue;in the second version - note that foreachwill fail on a null IEnumerableparameter
• allow filtering children with .Whereclause on the caller side or within the children selectorrather than passing a children filter selectorparameter:
  • it won't impact the efficiency because in both versions it is a deferred call
  • it would be mixing another logic with the method and I prefer to keep the logic separated

• 不允许展平 null IEnumerable，这可以通过删除异常抛出和：
  • 在第一个版本中添加source = source.EmptyIfNull();之前return
  • 在第二个版本if (source != null)之前添加foreach
• 允许选择器返回一个空集合 - 这样我就从调用者那里消除了责任以确保子列表不为空，这可以通过以下方式更改：
  • .EmptyIfNull()在第一个版本中删除- 请注意，SelectMany如果选择器返回 null ，则会失败
  • if (children == null) continue;在第二个版本中删除- 请注意这foreach将在空IEnumerable参数上失败
• 允许.Where在调用方或子选择器中使用子句过滤子项，而不是传递子过滤器选择器参数：
  • 它不会影响效率，因为在两个版本中它都是延迟调用
  • 它会将另一个逻辑与该方法混合，我更喜欢将逻辑分开

Sample use

样品使用

I'm using this extension method in LightSwitch to obtain all controls on the screen:

我在 LightSwitch 中使用这个扩展方法来获取屏幕上的所有控件：

public static class ScreenObjectExtensions
{
    public static IEnumerable<IContentItemProxy> FindControls(this IScreenObject screen)
    {
        var model = screen.Details.GetModel();

        return model.GetChildItems()
            .SelectManyRecursive(c => c.GetChildItems())
            .OfType<IContentItemDefinition>()
            .Select(c => screen.FindControl(c.Name));
    }
}

回答by Aidin

I had to implement mine from scratch because all of the provided solutions would break in case there is a loop i.e. a child that points to its ancestor. If you have the same requirements as mine please take a look at this (also let me know if my solution would break in any special circumstances):

我必须从头开始实现我的，因为如果有一个循环，即一个指向其祖先的孩子，所有提供的解决方案都会中断。如果您有与我相同的要求，请看一下这个（如果我的解决方案在任何特殊情况下会中断，也请告诉我）：

How to use:

如何使用：

var flattenlist = rootItem.Flatten(obj => obj.ChildItems, obj => obj.Id)

Code:

代码：

public static class Extensions
    {
        /// <summary>
        /// This would flatten out a recursive data structure ignoring the loops. The end result would be an enumerable which enumerates all the
        /// items in the data structure regardless of the level of nesting.
        /// </summary>
        /// <typeparam name="T">Type of the recursive data structure</typeparam>
        /// <param name="source">Source element</param>
        /// <param name="childrenSelector">a function that returns the children of a given data element of type T</param>
        /// <param name="keySelector">a function that returns a key value for each element</param>
        /// <returns>a faltten list of all the items within recursive data structure of T</returns>
        public static IEnumerable<T> Flatten<T>(this IEnumerable<T> source,
            Func<T, IEnumerable<T>> childrenSelector,
            Func<T, object> keySelector) where T : class
        {
            if (source == null)
                throw new ArgumentNullException("source");
            if (childrenSelector == null)
                throw new ArgumentNullException("childrenSelector");
            if (keySelector == null)
                throw new ArgumentNullException("keySelector");
            var stack = new Stack<T>( source);
            var dictionary = new Dictionary<object, T>();
            while (stack.Any())
            {
                var currentItem = stack.Pop();
                var currentkey = keySelector(currentItem);
                if (dictionary.ContainsKey(currentkey) == false)
                {
                    dictionary.Add(currentkey, currentItem);
                    var children = childrenSelector(currentItem);
                    if (children != null)
                    {
                        foreach (var child in children)
                        {
                            stack.Push(child);
                        }
                    }
                }
                yield return currentItem;
            }
        }

        /// <summary>
        /// This would flatten out a recursive data structure ignoring the loops. The     end result would be an enumerable which enumerates all the
        /// items in the data structure regardless of the level of nesting.
        /// </summary>
        /// <typeparam name="T">Type of the recursive data structure</typeparam>
        /// <param name="source">Source element</param>
        /// <param name="childrenSelector">a function that returns the children of a     given data element of type T</param>
        /// <param name="keySelector">a function that returns a key value for each   element</param>
        /// <returns>a faltten list of all the items within recursive data structure of T</returns>
        public static IEnumerable<T> Flatten<T>(this T source, 
            Func<T, IEnumerable<T>> childrenSelector,
            Func<T, object> keySelector) where T: class
        {
            return Flatten(new [] {source}, childrenSelector, keySelector);
        }
    }