递归列表展平

Question

我本可以自己写这个,但是我想要完成它的具体方法就是把我扔掉.我正在尝试编写一个类似于.NET 3.5中引入的其他通用扩展方法,它将采用IEnumerables的嵌套IEnumerable(依此类推)并将其展平为一个IEnumerable.有人有主意吗？

具体来说,我遇到了扩展方法本身的语法问题,因此我可以处理展平算法.

Answer 1

这是一个可能有帮助的扩展.它将遍历对象层次结构中的所有节点,并选择符合条件的节点.它假定层次结构中的每个对象都有一个包含其子对象的collection属性.

这是扩展名:

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

Answer 2

嗯......我不知道究竟你想要的这里,但这里有一个"一平"的选项:

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

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

这有帮助吗？

Answer 3

我以为我会分享一个完整的例子,包括错误处理和单逻辑应用程序.

递归展平很简单:

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

设计决策

我决定:

• 禁止展平null IEnumerable,可以通过删除异常抛出来改变:
  • 在第一个版本source = source.EmptyIfNull();之前添加return
  • 在第二个版本if (source != null)之前添加foreach
• 允许选择器返回null集合 - 这样我就从调用者中删除了责任,以确保子列表不为空,这可以通过以下方式更改:
  • .EmptyIfNull()在第一个版本中删除- 请注意,SelectMany如果选择器返回null ,则会失败
  • if (children == null) continue;在第二个版本中删除- 请注意,foreach在null IEnumerable参数上将失败
• 允许.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 4

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

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

Answer 5

这是修改后的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 6

功能：

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

        var descendants = nodes
                            .SelectMany(selector)
                            .RecursiveSelector(selector);

        return nodes.Concat(descendants);
    } 
}

用法：

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