c# - subcarpetas - Apilamiento de lista recursiva

recursividad c#

Question

Probablemente podría escribir esto yo mismo, pero la forma específica en que estoy tratando de lograrlo es echarme. Estoy intentando escribir un método de extensión genérico similar a los otros introducidos en .NET 3.5 que tomará un IEnumerable anidado de IEnumerables (y así sucesivamente) y lo aplanará en un IEnumerable. ¿Alguien tiene alguna idea?

Específicamente, tengo problemas con la sintaxis del método de extensión en sí mismo para poder trabajar en un algoritmo de aplanamiento.

Answer 1

¿No es eso para lo que [SelectMany] [1] es?

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

Answer 2

Aquí hay una respuesta modificada de Jon Skeet para permitir más que "un nivel":

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

descargo de responsabilidad: no sé C #.

Lo mismo en 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=" ")

Imprime:

1 2 3 4 5 6 7 8 

Answer 3

Aquí hay una extensión que podría ayudar. Atravesará todos los nodos en su jerarquía de objetos y seleccionará los que coincidan con un criterio. Asume que cada objeto en su jerarquía tiene una propiedad de colección que contiene sus objetos secundarios.

Aquí está la extensión:

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

Ejemplos (pruebas unitarias):

Primero necesitamos un objeto y una jerarquía de objetos anidados.

Una clase de nodo simple

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

Y un método para obtener una jerarquía profunda de nodos de 3 niveles

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

Primera prueba: aplanar la jerarquía, no filtrar

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

Esto mostrará:

Node 1, Level 1
Node 6, Level 1
Node 2, Level 2
Node 3, Level 2
Node 4, Level 3
Node 5, Level 3

Segunda prueba: obtenga una lista de nodos que tengan un NodeId con número par

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

Esto mostrará:

Node 6, Level 1
Node 2, Level 2
Node 4, Level 3

Answer 4

Básicamente, necesitas tener un IENumerable maestro que esté fuera de tu función recursiva, luego en tu función recursiva (código Psuedo)

private void flattenList(IEnumerable<T> list)
{
    foreach (T item in list)
    {
        masterList.Add(item);

        if (item.Count > 0)
        {
            this.flattenList(item);
        }
    }
}

Aunque realmente no estoy seguro de lo que quieres decir con IEnumerable anidado en un IEnumerable ... ¿qué hay dentro de eso? ¿Cuántos niveles de anidación? ¿Cuál es el tipo final? obviamente mi código no es correcto, pero espero que te haga pensar.

Answer 5

Dado que el rendimiento no está disponible en VB y LINQ proporciona tanto la ejecución diferida como una sintaxis concisa, también puede usar.

<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

Answer 6

De acuerdo, aquí hay otra versión que se combina con aproximadamente 3 respuestas anteriores.

Recursivo. Utiliza el rendimiento. Genérico. Predicado de filtro opcional. Función de selección opcional. Casi tan conciso como pude hacerlo.

    public static IEnumerable<TNode> Flatten<TNode>(
        this IEnumerable<TNode> nodes, 
        Func<TNode, bool> filterBy = null,
        Func<TNode, IEnumerable<TNode>> selectChildren = null
        )
    {
        if (nodes == null) yield break;
        if (filterBy != null) nodes = nodes.Where(filterBy);

        foreach (var node in nodes)
        {
            yield return node;

            var children = (selectChildren == null)
                ? node as IEnumerable<TNode>
                : selectChildren(node);

            if (children == null) continue;

            foreach (var child in children.Flatten(filterBy, selectChildren))
            {
                yield return child;
            }
        }
    }

Uso:

// With filter predicate, with selection function
var flatList = nodes.Flatten(n => n.IsDeleted == false, n => n.Children);

Answer 7

El método de extensión SelectMany ya lo hace.

Proyecta cada elemento de una secuencia a un IEnumerable <(Of <(T>)>) y aplana las secuencias resultantes en una secuencia.

Answer 8

Función:

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

        return nodes;
    } 
}

Uso:

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

Answer 9

Hmm ... No estoy seguro exactamente de lo que quieres aquí, pero aquí hay una opción de "un nivel":

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

Si eso no es lo que quieres, ¿podrías proporcionar la firma de lo que quieres? Si no necesita un formulario genérico, y solo desea hacer el tipo de cosas que hacen los constructores de LINQ a XML, eso es razonablemente simple, aunque el uso recursivo de bloques de iteradores es relativamente ineficiente. Algo como:

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

Tenga en cuenta que eso tratará una cadena como una secuencia de caracteres, sin embargo, es posible que desee que las cadenas de casos especiales sean elementos individuales en lugar de aplanarlos, según su caso de uso.

¿Eso ayuda?

Answer 10

Pensé que compartiría un ejemplo completo con el manejo de errores y un apporoach de lógica única.

El aplanamiento recursivo es tan simple como:

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

Versión no 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;
            }
        }
    }
}

Decisiones de diseño

Yo decidí:

• no permitir el aplanamiento de un IEnumerable nulo, esto se puede cambiar eliminando el lanzamiento de excepción y:
  • agregando source = source.EmptyIfNull(); antes de return en la primera versión
  • agregando if (source != null) antes de foreach en la segunda versión
• Permitir el retorno de una colección nula por parte del selector. De esta forma eliminaré la responsabilidad de la persona que llama para asegurar que la lista de niños no esté vacía, esto se puede cambiar de la siguiente manera:
  • eliminando .EmptyIfNull() en la primera versión, tenga en cuenta que SelectMany fallará si el selector devuelve null
  • eliminando if (children == null) continue; en la segunda versión, tenga en cuenta que foreach fallará en un parámetro IEnumerable nulo
• Permitir filtrar a los niños con la cláusula .Where en el lado de la persona que llama o dentro del selector de niños en lugar de pasar un parámetro selector de filtro secundario:
  • no afectará la eficiencia porque en ambas versiones es una llamada diferida
  • sería mezclar otra lógica con el método y prefiero mantener la lógica separada

Uso de muestra

Estoy usando este método de extensión en LightSwitch para obtener todos los controles en la pantalla:

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 11

Tuve que implementar el mío desde cero porque todas las soluciones proporcionadas se romperían en caso de que hubiera un ciclo, es decir, un niño que apuntara a su antecesor. Si tiene los mismos requisitos que los míos, eche un vistazo a esto (también avíseme si mi solución se rompería en circunstancias especiales):

Cómo utilizar:

var flattenlist = rootItem.Flatten(obj => obj.ChildItems, obj => obj.Id)

Código:

public static class Extensions
    {
        /// <summary>
        /// This would flatten out a recursive data structure ignoring the loops. The end result would be an enumerable which enumerates all the
        /// items in the data structure regardless of the level of nesting.
        /// </summary>
        /// <typeparam name="T">Type of the recursive data structure</typeparam>
        /// <param name="source">Source element</param>
        /// <param name="childrenSelector">a function that returns the children of a given data element of type T</param>
        /// <param name="keySelector">a function that returns a key value for each element</param>
        /// <returns>a faltten list of all the items within recursive data structure of T</returns>
        public static IEnumerable<T> Flatten<T>(this IEnumerable<T> source,
            Func<T, IEnumerable<T>> childrenSelector,
            Func<T, object> keySelector) where T : class
        {
            if (source == null)
                throw new ArgumentNullException("source");
            if (childrenSelector == null)
                throw new ArgumentNullException("childrenSelector");
            if (keySelector == null)
                throw new ArgumentNullException("keySelector");
            var stack = new Stack<T>( source);
            var dictionary = new Dictionary<object, T>();
            while (stack.Any())
            {
                var currentItem = stack.Pop();
                var currentkey = keySelector(currentItem);
                if (dictionary.ContainsKey(currentkey) == false)
                {
                    dictionary.Add(currentkey, currentItem);
                    var children = childrenSelector(currentItem);
                    if (children != null)
                    {
                        foreach (var child in children)
                        {
                            stack.Push(child);
                        }
                    }
                }
                yield return currentItem;
            }
        }

        /// <summary>
        /// This would flatten out a recursive data structure ignoring the loops. The     end result would be an enumerable which enumerates all the
        /// items in the data structure regardless of the level of nesting.
        /// </summary>
        /// <typeparam name="T">Type of the recursive data structure</typeparam>
        /// <param name="source">Source element</param>
        /// <param name="childrenSelector">a function that returns the children of a     given data element of type T</param>
        /// <param name="keySelector">a function that returns a key value for each   element</param>
        /// <returns>a faltten list of all the items within recursive data structure of T</returns>
        public static IEnumerable<T> Flatten<T>(this T source, 
            Func<T, IEnumerable<T>> childrenSelector,
            Func<T, object> keySelector) where T: class
        {
            return Flatten(new [] {source}, childrenSelector, keySelector);
        }
    }

Answer 12

class PageViewModel { 
    public IEnumerable<PageViewModel> ChildrenPages { get; set; } 
}

Func<IEnumerable<PageViewModel>, IEnumerable<PageViewModel>> concatAll = null;
concatAll = list => list.SelectMany(l => l.ChildrenPages.Any() ? 
    concatAll(l.ChildrenPages).Union(new[] { l }) : new[] { l });

var allPages = concatAll(source).ToArray();

Answer 13

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

Tal vez así? ¿O quiere decir que podría ser infinitamente profundo?