recursion列表展平

我可以自己写这个，但是我试图完成的具体方式是把我扔掉。 我正在尝试编写一个类似于.NET 3.5中引入的通用扩展方法，该扩展方法将嵌套IEnumerable的IEnumerables（等等）并将其扁平化为一个IEnumerable。 任何人有任何想法？

具体来说，我遇到了扩展方法本身的语法问题，所以我可以使用flatteningalgorithm。

Answer 1

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

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; } } } 

如果这不是你想要的，你能提供你想要的签名吗？ 如果你不需要一个通用的表单，而你只是想做一些LINQ to XML构造函数，那么这样做相当简单 – 虽然迭代器块的recursion使用效率相对较低。 就像是：

 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; } } } 

请注意，这将把一个string视为一个字符序列，但是 – 根据您的使用情况，您可能希望将特殊string作为单独的元素，而不是将其扁平化。

这有帮助吗？

Answer 2

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

这是扩展名：

 /// 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; } 

示例（unit testing）：

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

一个简单的节点类

 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); } } 

还有一种获得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; } 

第一次testing：扁平化层次结构，不进行过滤

 [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()); } 

这将显示：

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

第二次testing：获取具有偶数编号的节点的节点列表

 [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()); } 

这将显示：

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

Answer 3

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

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

Answer 4

这是一个修改后的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; } } } 

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

在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=" ") 

它打印：

 1 2 3 4 5 6 7 8 

Answer 5

我想我会分享一个error handling和一个单一的逻辑approach完整的例子。

recursion展平就像下面这样简单：

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>(); } } 

非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; } } } } 

devise决策

我决定：

• 不允许展开一个null IEnumerable ，这可以通过移除exception抛出来改变：
  • joinsource = source.EmptyIfNull(); 在return第一版之前
  • 在第二版本的foreach之前添加if (source != null)
• 允许通过select器返回一个空集合 – 这样我就可以从调用者中除去责任，以确保子列表不是空的，这可以通过以下方式进行更改：
  • 在第一个版本中删除.EmptyIfNull() – 注意如果select器返回null， SelectMany将会失败
  • 删除if (children == null) continue; 在第二个版本中 – 请注意， foreach将失败一个空的IEnumerable参数
• 允许在调用者端或子select器内使用.Where子句筛选子项，而不是传递子筛选器参数：
  • 它不会影响效率，因为在这两个版本中它是一个延期的呼叫
  • 它将混合另一个逻辑的方法，我宁愿保持逻辑分离

示例使用

我在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)); } } 

Answer 6

SelectMany扩展方法已经这样做了。

将序列的每个元素投影到IEnumerable <（Of <（T>）>），并将结果序列展平成一个序列。

Answer 7

既然yield在VB中不可用，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 

Answer 8

我必须从头开始实施，因为所有提供的解决scheme都会在有回路的情况下破裂，即指向其祖先的孩子。 如果你有和我一样的要求，请看看这个（也请告诉我，如果我的解决scheme在任何特殊情况下都会中断的话）：

如何使用：

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

码：

 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); } } 

Answer 9

function：

 public static class MyExtentions { public static IEnumerable<T> RecursiveSelector<T>(this IEnumerable<T> nodes, Func<T, IEnumerable<T>> selector) { if(nodes.Any()) return nodes.Concat(nodes.SelectMany(selector).RecursiveSelector(selector)); return nodes; } } 

用法：

 var ar = new[] { new Node { Name = "1", Chilren = new[] { new Node { Name = "11", Children = new[] { new Node { Name = "111", } } } } } }; var flattened = ar.RecursiveSelector(x => x.Children).ToList(); 

Answer 10

 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; } } 

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

Answer 11

基本上，你需要有一个主要的IENumerable在你的recursion函数之外，那么在你的recursion函数（Psuedo-code）

 private void flattenList(IEnumerable<T> list) { foreach (T item in list) { masterList.Add(item); if (item.Count > 0) { this.flattenList(item); } } } 

虽然我真的不知道你的意思是IEnumerable嵌套在一个IEnumerable中…那是什么？ 多less层次的嵌套？ 最后的types是什么？ 显然我的代码是不正确的，但我希望它让你思考。