Aplanamiento de lista recursiva

StackOverflow https://stackoverflow.com/questions/141467

  •  02-07-2019
  •  | 
  •  

Pregunta

Probablemente podría escribir esto yo mismo, pero la forma específica en que estoy tratando de lograrlo me está desanimando. Estoy tratando de 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.

¿Fue útil?

Solución

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

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 una forma genérica, y solo desea hacer el tipo de cosas que hacen los constructores de LINQ to XML, eso es razonablemente simple, aunque el uso recursivo de bloques iteradores es relativamente ineficiente. Algo así 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 aplanarlas, dependiendo de su caso de uso.

¿Eso ayuda?

Otros consejos

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. Se supone 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, sin filtrado 

[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 tienen un NodeId de 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

Pensé en compartir un ejemplo completo con manejo de errores y un enfoque lógico único.

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

Decidí:

  • no permite aplanar un nulo IEnumerable, esto se puede cambiar eliminando el lanzamiento de excepciones 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 que el selector devuelva una colección nula; de esta forma, elimino la responsabilidad de la persona que llama para asegurar que la lista de niños no esté vacía, esto se puede cambiar mediante:
    • eliminando .EmptyIfNull() en la primera versión: tenga en cuenta que SelectMany fallará si el selector devuelve nulo
    • eliminando if (children == null) continue; en la segunda versión: tenga en cuenta que .Where fallará en un parámetro nulo <=>
  • permite filtrar elementos secundarios con la cláusula <=> en el lado del llamante o dentro del selector de elementos secundarios en lugar de pasar un parámetro selector de filtro de elementos secundarios :
    • no afectará la eficiencia porque en ambas versiones es una llamada diferida
    • estaría mezclando otra lógica con el método y prefiero mantener la lógica separada

Ejemplo de uso

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

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

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

Aquí hay una respuesta de Jon Skeet modificada para permitir más de " one 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

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

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

  

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

Dado que el rendimiento no está disponible en VB y LINQ proporciona ejecución diferida y 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

Tuve que implementar la mía desde cero porque todas las soluciones proporcionadas se romperían en caso de que haya un bucle, es decir, un niño que apunte a su antepasado. 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 alguna circunstancia especial):

Cómo usar: 

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

Bien, aquí hay otra versión que se combina de aproximadamente 3 respuestas anteriores.

Recursivo. Utiliza rendimiento. Genérico. Predicador de filtro opcional. Función de selección opcional. 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);

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

¿Quizás así? ¿O quiere decir que podría ser poco profundo? 

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

Básicamente, debe tener un maestro IENumerable que esté fuera de su función recursiva, luego en su 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 anidamiento? ¿Cuál es el tipo final? obviamente mi código no es correcto, pero espero que te haga pensar.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top