c# - Cómo "desenrollar" una estructura "recursiva"

recursion ienumerable

Question

No estoy seguro de cómo llamarlo, pero digamos que tiene una clase que se ve así:

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

Luego tiene una persona y desea "desenrollar" esta estructura de manera recursiva, de modo que termine con una sola lista de todas las personas sin duplicados.

¿Cómo harías esto? Ya he hecho algo que parece estar funcionando, pero tengo curiosidad por ver cómo lo harían otros y, especialmente, si hay algo integrado en Linq que puede usar de una manera inteligente para resolver este pequeño problema :)

Aquí está mi solución:

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

Se usaría algo como esto:

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

Answer 1

Aquí hay una implementación que:

• Selecciona primero una profundidad recursiva,
• No requiere doble iteración de las colecciones secundarias,
• No usa colecciones intermedias para los elementos seleccionados,
• No maneja ciclos,

• Puede hacerlo al revés

  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 2

Encontré esta pregunta como estaba buscando y pensando en una solución similar, en mi caso creando un eficiente IEnumerable<Control> para controles de interfaz de usuario ASP.NET. El yield recursivo que tuve fue rápido, pero sabía que podría tener un costo adicional, ya que cuanto más profunda era la estructura de control, más tiempo podía tomar. Ahora sé que esto es O (n log n).

La solución que se brinda aquí brinda alguna respuesta, pero, como se discutió en los comentarios, sí cambia el orden (que al OP no le importa). Me di cuenta de que para preservar el orden dado por el OP y cuando lo necesitaba, ni una Queue simple (como la usó Jon) ni Stack funcionarían, ya que todos los objetos primarios serían cedidos primero y luego los secundarios después de ellos (o viceversa). )

Para resolver esto y conservar el orden, me di cuenta de que la solución sería simplemente poner el Enumerator en una Stack . Para usar la pregunta original de OPs se vería así:

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

Uso stack.Peek aquí para no tener que volver a stack.Peek el mismo enumerador en la pila, ya que es probable que sea la operación más frecuente, esperando que el enumerador proporcione más de un elemento.

Esto crea el mismo número de enumeradores que en la versión recursiva, pero probablemente habrá menos objetos nuevos que colocar todos los temas en una cola o pila y continuar agregando cualquier tema descendiente. Este es el tiempo O (n) ya que cada enumerador se sostiene por sí mismo (en la versión recursiva, una llamada implícita a un MoveNext ejecuta MoveNext en los enumeradores hijos a la profundidad actual en la pila de recursión).

Answer 3

La recursión es siempre divertida. Tal vez podrías simplificar tu código para:

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 || !subjects.Any())
        return Enumerable.Empty<T>();

    // Gather a list of all (selected) child elements of all subjects
    var subjectChildren = subjects.SelectMany(selector);

    // Jump into the recursion for each of the child elements
    var recursiveChildren = SelectRecursive(subjectChildren, selector);

    // Combine the subjects with all of their (recursive child elements).
    // The union will remove any direct parent-child duplicates.
    // Endless loops due to circular references are however still possible.
    return subjects.Union(recursiveChildren);
}

Producirá menos duplicados que tu código original. Sin embargo, es posible que sus duplicados causen un bucle infinito, la unión solo evitará duplicados directos de padres e hijos.

Y el orden de los artículos será diferente al tuyo :)

Editar: Cambió la última línea de código a tres declaraciones y agregó un poco más de documentación.

Answer 4

No creo que haya algo incorporado en LINQ para hacer esto.

Hay un problema al hacerlo recursivamente de esta manera: terminas creando una gran cantidad de iteradores. Esto puede ser bastante ineficiente si el árbol es profundo. Wes Dyer y Eric Lippert han blogueado sobre esto.

Puede eliminar esta ineficacia eliminando la recursión directa. Por ejemplo:

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

Esto también cambiará el orden de iteración: se convierte primero en ancho primero en lugar de primero en profundidad; reescribirlo para seguir siendo primero en profundidad es complicado. También lo cambié para no usar Any() : esta versión revisada no evaluará ninguna secuencia más de una vez, lo que puede ser útil en algunos escenarios. Esto tiene un problema, claro, llevará más memoria, debido a las colas. Probablemente podríamos aliviar esto almacenando una cola de iteradores en lugar de elementos, pero no estoy seguro de que sea ... sin duda sería más complicado.

Un punto a tener en cuenta (también notado por ChrisW mientras buscaba las publicaciones del blog :) - si tiene ciclos en su lista de amigos (es decir, si A tiene B y B tiene A), recurrirá para siempre.

Answer 5

También podría usar un método no recursivo como este:

  HashSet<Person> GatherAll (Person p) {
     Stack<Person> todo = new Stack<Person> ();
     HashSet<Person> results = new HashSet<Person> ();
     todo.Add (p); results.Add (p);
     while (todo.Count > 0) {
        Person p = todo.Pop (); 
        foreach (Person f in p.Friends) 
           if (results.Add (f)) todo.Add (f);
     }
     return results;
  }

Esto también debería manejar los ciclos correctamente. Estoy empezando con una sola persona, pero podría expandir esto fácilmente para comenzar con una lista de personas.

Answer 6

usa la extensión Agregado ...

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