Cómo "desenrollar" una estructura "recursivo"

Question

No estoy seguro de cómo llamarlo, pero supongamos que tiene una clase que tiene este aspecto:

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

A continuación, tiene una persona y que desea "desenrollar" esta estructura de manera recursiva, por lo que terminas 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 los demás 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

no creo que haya nada integrado en LINQ para hacer esto.

Hay un problema al hacerlo recursivamente de esta manera: termina 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 en primero en anchura 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) entonces recurse Siempre.

Answer 2

Se puede usar un método no recursivo como esto, así:

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 debe manejar adecuadamente los ciclos también. I am comenzando con una sola persona, pero podría ampliarlo fácilmente para comenzar con una lista de personas.

Answer 3

La recursividad es siempre divertida. Tal vez podría simplificar su código a:

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 el 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 elementos será diferente de la suya :)

Editar: Un cambio en la última línea de código a tres declaraciones y añadió un poco más documentación.

Answer 4

utilizar la extensión Agregar ...

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 5

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

La solución dada aquí proporciona alguna respuesta, pero, como se comenta en los comentarios, cambia el orden (que al OP no le importaba). Me di cuenta de que para preservar el orden dado por el OP y cuando lo necesitaba, ni un simple Queue (como lo usaba Jon) ni Stack funcionaría dado que todos los objetos principales 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 un Stack. Para utilizar el PO pregunta original que 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(); 
     } 
    } 
} 

utilizo stack.Peek aquí para evitar tener que empujar el mismo encuestador de nuevo en la pila, ya que es probable que sea la operación más frecuente, esperando que enumerador para proporcionar 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 uno MoveNext ejecuta MoveNext en los enumeradores hijo a la profundidad actual en la pila de recursión).

Answer 6

Aquí es una implementación que:

• ¿Un profundidad recursiva primera selección,
• No requiere doble iteración de las colecciones hijas,
• No usa colecciones intermedias de 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(); 
       } 
      } 
  }