Appiattimento elenco ricorsivo

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

  •  02-07-2019
  •  | 
  •  

Domanda

Probabilmente potrei scriverlo da solo, ma il modo specifico in cui sto provando a realizzarlo mi sta buttando via. Sto cercando di scrivere un metodo di estensione generico simile agli altri introdotti in .NET 3.5 che prenderà un IEnumerable nidificato di IEnumerables (e così via) e lo appiattirà in un IEnumerable. Qualcuno ha qualche idea?

In particolare, sto riscontrando problemi con la sintassi del metodo di estensione stesso in modo da poter lavorare su un algoritmo appiattimento.

È stato utile?

Soluzione

Hmm ... Non sono sicuro esattamente cosa vuoi qui, ma ecco un " un livello " Opzione: 

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

Se non è quello che vuoi, potresti fornire la firma di ciò che vuoi? Se non hai bisogno di un modulo generico e vuoi semplicemente fare il tipo di cose che fanno i costruttori LINQ to XML, questo è ragionevolmente semplice, sebbene l'uso ricorsivo dei blocchi iteratori sia relativamente inefficiente. Qualcosa del tipo: 

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

Nota che ciò tratterà una stringa come una sequenza di caratteri, tuttavia - potresti voler usare stringhe di casi speciali come singoli elementi invece di appiattirli, a seconda del tuo caso d'uso.

Aiuta?

Altri suggerimenti

Ecco un'estensione che potrebbe aiutare. Attraverserà tutti i nodi nella gerarchia degli oggetti e selezionerà quelli che corrispondono a un criterio. Presuppone che ogni oggetto nella tua gerarchia abbia una proprietà di raccolta che contiene i suoi oggetti figlio.

Ecco l'estensione: 

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

Esempi (Test unitari):

Per prima cosa abbiamo bisogno di un oggetto e di una gerarchia di oggetti nidificati.

Una semplice classe di nodi 

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

E un metodo per ottenere una gerarchia profonda di nodi a 3 livelli 

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

Primo test: appiattire la gerarchia, nessun filtro 

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

Questo mostrerà: 

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

Secondo test: ottieni un elenco di nodi con un NodeId con numero pari 

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

Questo mostrerà: 

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

Ho pensato di condividere un esempio completo con la gestione degli errori e un approccio a logica singola.

L'appiattimento ricorsivo è semplice come:

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

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

Decisioni di progettazione

Ho deciso di:

  • non consente di appiattire un null IEnumerable, questo può essere modificato rimuovendo il lancio di eccezioni e:
    • aggiungendo source = source.EmptyIfNull(); prima di return nella prima versione
    • aggiungendo if (source != null) prima di foreach nella seconda versione
  • consenti la restituzione di una raccolta nulla da parte del selettore: in questo modo rimuovo la responsabilità dal chiamante per assicurare che l'elenco di figli non sia vuoto, questo può essere modificato da:
    • rimozione di .EmptyIfNull() nella prima versione. Nota che SelectMany fallirà se il selettore restituisce null
    • rimozione di if (children == null) continue; nella seconda versione. Tieni presente che .Where fallirà su un <=> parametro null
  • consente di filtrare i bambini con la clausola <=> sul lato chiamante o all'interno del selettore figli anziché passare un parametro selettore filtri figli :
    • non influirà sull'efficienza perché in entrambe le versioni è una chiamata differita
    • sarebbe mescolare un'altra logica con il metodo e preferisco mantenere la logica separata

Esempio di utilizzo

Sto usando questo metodo di estensione in LightSwitch per ottenere tutti i controlli sullo schermo: 

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

Non è per questo che [SelectMany] [1] è? 

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

Ecco una risposta di Jon Skeet modificata per consentire più di " una livello quot &; 

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

disclaimer: non conosco C #.

Lo stesso in 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=" ")

Stampa: 

1 2 3 4 5 6 7 8

funzione: 

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

Utilizzo: 

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

L'estensione SelectMany il metodo lo fa già.

  

Proietta ogni elemento di una sequenza su   un IEnumerable < (Of < (T >) >) e   appiattisce le sequenze risultanti in   una sequenza.

Poiché la resa non è disponibile in VB e LINQ fornisce sia un'esecuzione differita che una sintassi concisa, puoi anche usare. 

<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

Ho dovuto implementare il mio da zero perché tutte le soluzioni fornite si romperanno nel caso in cui ci sia un ciclo, cioè un bambino che punta al suo antenato. Se hai gli stessi requisiti dei miei, ti preghiamo di dare un'occhiata a questo (fammi sapere anche se la mia soluzione si romperà in circostanze particolari):

Come usare: 

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

Codice: 

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

Ok, ecco un'altra versione che è combinata da circa 3 risposte sopra.

ricorsiva. Usa la resa. Generico. Predicato filtro opzionale. Funzione di selezione opzionale. Circa il più conciso possibile. 

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

Utilizzo: 

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

Forse in questo modo? O vuoi dire che potrebbe essere potenzialmente profondamente profondo? 

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

Fondamentalmente, devi avere un master IENumerable che è al di fuori della tua funzione ricorsiva, quindi nella tua funzione ricorsiva (Psuedo-code) 

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

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

Anche se non sono davvero sicuro di cosa intendi per IEnumerable nidificato in un IEnumerable ... cosa c'è dentro? Quanti livelli di nidificazione? Qual è il tipo finale? ovviamente il mio codice non è corretto, ma spero che ti faccia pensare.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top