递归列表展平
时间：2020-03-06 14:48:12 来源:igfitidea点击:
我可能可以自己写这篇文章，但是我试图实现这一目标的特定方式却使我失望。我正在尝试编写一种与.NET 3.5中引入的扩展方法类似的通用扩展方法，该方法将嵌套IEnumerable的IEnumerables(依此类推)，并将其展平为一个IEnumerable。有人有想法么？
具体来说，我在扩展方法本身的语法方面遇到麻烦，因此我无法使用展平算法。
解决方案
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，它在递归函数之外，然后在递归函数中(伪代码)
private void flattenList(IEnumerable<T> list)
{
foreach (T item in list)
{
masterList.Add(item);
if (item.Count > 0)
{
this.flattenList(item);
}
}
}
虽然我真的不确定我们嵌套在IEnumerable中的IEnumerable的含义是什么？有多少层嵌套？最终的类型是什么？显然我的代码不正确，但是我希望它能引起思考。
嗯...我不确定我们想要的是什么，但是这里有一个"一级"选项：
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构造函数那样的事情，那是相当简单的，尽管递归使用迭代器块效率相对较低。就像是：
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;
}
}
}
请注意，这会将字符串视为字符序列，但是，根据用例，我们可能希望将特殊情况下的字符串作为单独的元素，而不是将它们展平。
有帮助吗？
这不是[SelectMany] [1]的目的吗？
enum1.SelectMany(
a => a.SelectMany(
b => b.SelectMany(
c => c.Select(
d => d.Name
)
)
)
);
这是一个可能有用的扩展。它将遍历对象层次结构中的所有节点，并挑选出符合条件的节点。它假定层次结构中的每个对象都有一个收集属性，该属性保存其子对象。
这是扩展名：
/// 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;
}
示例(单元测试)：
首先，我们需要一个对象和一个嵌套的对象层次结构。
一个简单的节点类
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;
}
第一次测试：整理层次结构，不进行过滤
[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
第二次测试：获取具有偶数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());
}
这将显示：
Node 6, Level 1 Node 2, Level 2 Node 4, Level 3
SelectMany扩展方法已经做到了。
Projects each element of a sequence to an IEnumerable<(Of <(T>)>) and flattens the resulting sequences into one sequence.
这是乔恩·斯凯特(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
由于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
