recursion列表展平
我可以自己写这个,但是我试图完成的具体方式是把我扔掉。 我正在尝试编写一个类似于.NET 3.5中引入的通用扩展方法,该扩展方法将嵌套IEnumerable的IEnumerables(等等)并将其扁平化为一个IEnumerable。 任何人有任何想法?
具体来说,我遇到了扩展方法本身的语法问题,所以我可以使用flatteningalgorithm。
嗯…我不确定你到底想要什么,但是这里有一个“一级”选项:
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作为单独的元素,而不是将其扁平化。
这有帮助吗?
这是一个可能有所帮助的扩展。 它将遍历对象层次结构中的所有节点,并挑选出符合条件的节点。 它假定层次结构中的每个对象都有一个保存其子对象的集合属性 。
这是扩展名:
/// 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
这不是[SelectMany] [1]的用途吗?
enum1.SelectMany( a => a.SelectMany( b => b.SelectMany( c => c.Select( d => d.Name ) ) ) );
这是一个修改后的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
我想我会分享一个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抛出来改变:- join
source = source.EmptyIfNull();
在return
第一版之前 - 在第二版本的
foreach
之前添加if (source != null)
- join
- 允许通过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)); } }
SelectMany
扩展方法已经这样做了。
将序列的每个元素投影到IEnumerable <(Of <(T>)>),并将结果序列展平成一个序列。
既然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
我必须从头开始实施,因为所有提供的解决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); } }
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();
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; } }
也许这样? 或者你的意思是它可能是无限深的?
基本上,你需要有一个主要的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是什么? 显然我的代码是不正确的,但我希望它让你思考。