如何“展开”“递归”结构

Question

不确定如何调用，但是说您有一个看起来像这样的类：

class Person
{
    public string Name;
    public IEnumerable<Person> Friends;
}

然后您有了一个人，并且您希望递归“展开”此结构，因此最终只能得到所有人的唯一列表，没有重复项。

您将如何做？我已经做了一些看起来可行的事情，但是我很好奇看到其他人会怎么做，特别是如果Linq内置了一些东西，您可以用一种聪明的方式来解决这个小问题：）

---

这是我的解决方法：

public static IEnumerable<T> SelectRecursive<T>(this IEnumerable<T> subjects, Func<T, IEnumerable<T>> selector)
{
    // Stop if subjects are null or empty
    if(subjects == null)
        yield break;

    // For each subject
    foreach(var subject in subjects)
    {
        // Yield it
        yield return subject;

        // Then yield all its decendants
        foreach (var decendant in SelectRecursive(selector(subject), selector))
            yield return decendant;
    }
}

将被使用这样的东西：

var people = somePerson.SelectRecursive(x => x.Friends);

Answer 1

以这种方式递归执行时会遇到问题-您最终创建了大量的迭代器。如果树很深，则效率可能很低。 Wes Dyer和Eric Lippert都为此写了博客。

您可以通过删除直接递归来消除这种效率低下的情况。例如：

public static IEnumerable<T> SelectRecursive<T>(this IEnumerable<T> subjects,
    Func<T, IEnumerable<T>> selector)
{
    if (subjects == null)
    {
        yield break;
    }

    Queue<T> stillToProcess = new Queue<T>(subjects);

    while (stillToProcess.Count > 0)
    {
        T item = stillToProcess.Dequeue();
        yield return item;
        foreach (T child in selector(item))
        {
            stillToProcess.Enqueue(child);
        }
    }
}

这还将更改迭代顺序-变为广度优先而不是深度优先；仍然将其重写为深度优先是很棘手的。我也将其更改为不使用Any()-此修订版不会多次评估任何序列，这在某些情况下可以派上用场。请注意，这确实有一个问题-由于排队，它将占用更多的内存。我们可以通过存储迭代器而不是项目的队列来减轻这种情况，但是我不确定用完之后……肯定会更复杂。

要注意的一点（我在查找博客文章时也由ChrisW指出：）-如果您的朋友列表中有任何循环（即，如果A有B，而B有A），那么您将永远递归。 

Answer 2

此处给出的解决方案提供了一些答案，但是，正如注释中所讨论的，它的确改变了顺序（OP不在乎）。我意识到，要保留OP给定的顺序并按我的需要，简单的Queue（按Jon的用法）或Stack都不会起作用，因为将首先产生所有父对象，然后才产生所有子对象（或相反）。

为了解决这个问题并保留顺序，我意识到解决方案只是将Enumerator本身放在Stack上。要使用OP的原始问题，它将看起来像这样：

public static IEnumerable<T> SelectRecursive<T>(this IEnumerable<T> subjects, Func<T, IEnumerable<T>> selector)
{
    if (subjects == null)
        yield break;

    var stack = new Stack<IEnumerator<T>>();

    stack.Push(subjects.GetEnumerator());

    while (stack.Count > 0)
    {
        var en = stack.Peek();
        if (en.MoveNext())
        {
            var subject = en.Current;
            yield return subject;

            stack.Push(selector(subject).GetEnumerator());
        }
        else 
        {
            stack.Pop().Dispose();
        }
    }
}

我在这里使用stack.Peek来避免将相同的枚举数推回堆栈，因为这可能是更频繁的操作，希望该枚举数提供多个项。

这将创建与递归版本相同的枚举数，但是与将所有主题放入队列或堆栈并继续添加任何后代主题相比，新对象可能更少。这是O（n）时间，因为每个枚举器独立站立（在递归版本中，对一个MoveNext的隐式调用在子枚举器上执行MoveNext到递归堆栈中的当前深度）。

Answer 3

    List<Person> persons = GetPersons(); 
    List<Person> result = new List<Person>(); 
    persons.Aggregate(result,SomeFunc);

    private static List<Person> SomeFunc(List<Person> arg1,Person arg2)
    {
    arg1.Add(arg2)
    arg1.AddRange(arg2.Persons);
    return arg1;
    }

Answer 4

首先进行深度优先递归选择，>>

不需要子集合的两次迭代，
• 不对所选元素使用中间集合，
• 不处理循环，
• 可以向后做。

• public static IEnumerable<T> SelectRecursive<T>(this IEnumerable<T> rootItems, Func<T, IEnumerable<T>> selector)
  {
      return new RecursiveEnumerable<T>(rootItems, selector, false);
  }
  
  public static IEnumerable<T> SelectRecursiveReverse<T>(this IEnumerable<T> rootItems, Func<T, IEnumerable<T>> selector)
  {
      return new RecursiveEnumerable<T>(rootItems, selector, true);
  }
  
  class RecursiveEnumerable<T> : IEnumerable<T>
  {
      public RecursiveEnumerable(IEnumerable<T> rootItems, Func<T, IEnumerable<T>> selector, bool reverse)
      {
          _rootItems = rootItems;
          _selector = selector;
          _reverse = reverse;
      }
  
      IEnumerable<T> _rootItems;
      Func<T, IEnumerable<T>> _selector;
      bool _reverse;
  
      public IEnumerator<T> GetEnumerator()
      {
          return new Enumerator(this);
      }
  
      System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
      {
          return GetEnumerator();
      }
  
      class Enumerator : IEnumerator<T>
      {
          public Enumerator(RecursiveEnumerable<T> owner)
          {
              _owner = owner;
              Reset();
          }
  
          RecursiveEnumerable<T> _owner;
          T _current;
          Stack<IEnumerator<T>> _stack = new Stack<IEnumerator<T>>();
  
  
          public T Current
          {
              get 
              {
                  if (_stack == null || _stack.Count == 0)
                      throw new InvalidOperationException();
                  return _current; 
              }
          }
  
          public void Dispose()
          {
              _current = default(T);
              if (_stack != null)
              {
                  while (_stack.Count > 0)
                  {
                      _stack.Pop().Dispose();
                  }
                  _stack = null;
              }
          }
  
          object System.Collections.IEnumerator.Current
          {
              get { return Current; }
          }
  
          public bool MoveNext()
          {
              if (_owner._reverse)
                  return MoveReverse();
              else
                  return MoveForward();
          }
  
          public bool MoveForward()
          {
              // First time?
              if (_stack == null)
              {
                  // Setup stack
                  _stack = new Stack<IEnumerator<T>>();
  
                  // Start with the root items
                  _stack.Push(_owner._rootItems.GetEnumerator());
              }
  
              // Process enumerators on the stack
              while (_stack.Count > 0)
              {
                  // Get the current one
                  var se = _stack.Peek();
  
                  // Next please...
                  if (se.MoveNext())
                  {
                      // Store it
                      _current = se.Current;
  
                      // Get child items
                      var childItems = _owner._selector(_current);
                      if (childItems != null)
                      {
                          _stack.Push(childItems.GetEnumerator());
                      }
  
                      return true;
                  }
  
                  // Finished with the enumerator
                  se.Dispose();
                  _stack.Pop();
              }
  
              // Finished!
              return false;
          }
  
          public bool MoveReverse()
          {
              // First time?
              if (_stack == null)
              {
                  // Setup stack
                  _stack = new Stack<IEnumerator<T>>();
  
                  // Start with the root items
                  _stack.Push(_owner._rootItems.Reverse().GetEnumerator());
              }
  
              // Process enumerators on the stack
              while (_stack.Count > 0)
              {
                  // Get the current one
                  var se = _stack.Peek();
  
                  // Next please...
                  if (se.MoveNext())
                  {
                      // Get child items
                      var childItems = _owner._selector(se.Current);
                      if (childItems != null)
                      {
                          _stack.Push(childItems.Reverse().GetEnumerator());
                          continue;
                      }
  
                      // Store it
                      _current = se.Current;
                      return true;
                  }
  
                  // Finished with the enumerator
                  se.Dispose();
                  _stack.Pop();
  
                  if (_stack.Count > 0)
                  {
                      _current = _stack.Peek().Current;
                      return true;
                  }
              }
  
              // Finished!
              return false;
          }
  
          public void Reset()
          {
              Dispose();
          }
      }
  }

Answer 5

Answer 6