Rekursive Liste Abflachen

Question

Ich könnte wahrscheinlich die selbst schreiben, aber die spezifische Art, wie ich es bin versucht zu erreichen, wirft mich ab. Ich versuche, eine generische Erweiterungsmethode ähnlich wie die anderen .NET 3.5 eingeführt zu schreiben, der eine verschachtelte IEnumerable von IEnumerables nehmen (und so weiter) und glätten Sie es in ein IEnumerable. Wer irgendwelche Ideen?

Insbesondere Ich habe Probleme mit der Syntax der Erweiterungsmethode selbst, so dass ich auf einem Abflachen Algorithmus arbeiten kann.

Answer 1

Hmm ... Ich bin nicht sicher, genau , was Sie wollen hier, aber hier ist eine "one level" Option:

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

Wenn das nicht das, was Sie wollen, könnten Sie bieten die Signatur von dem, was Sie wollen? Wenn Sie nicht über eine generische Form benötigen, und Sie wollen einfach nur die Art der Sache zu tun, dass LINQ to XML Konstrukteuren tun, das ist ziemlich einfach - obwohl die rekursive Verwendung von Iterator Blöcke relativ ineffizient ist. So etwas wie:

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

Beachten Sie, dass die eine Zeichenfolge als eine Folge von Zeichen behandeln, aber -. Sie Spezialfall-Strings wollen können einzelne Elemente statt Abflachung sie, je nach Anwendungsfall

Ist diese Hilfe?

Answer 2

Hier ist eine Erweiterung, die helfen könnten. Es wird alle Knoten in der Hierarchie von Objekten durchquert und diejenigen, die ein Kriterium entsprechen auszusuchen. Er geht davon aus, dass jedes Objekt in der Hierarchie eine Sammlungseigenschaft , das seine untergeordneten Objekte enthält.

Hier ist die Erweiterung:

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

Beispiele (Unit Tests):

Zuerst müssen wir ein Objekt und eine verschachtelte Objekt-Hierarchie.

Eine einfache Knotenklasse

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

Und ein Verfahren zur Herstellung eine 3-stufige tiefe Hierarchie von Knoten erhalten

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

Erster Test: abflachen die Hierarchie, keine Filterung

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

Dies zeigt:

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

Zweiter Test: Hier finden Sie eine Liste von Knoten, die eine geradzahlige NodeId haben

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

Dies zeigt:

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

Answer 3

Ich dachte, ich würde ein vollständiges Beispiel mit Fehlerbehandlung teilen und einer Single-Logik apporoach.

rekursive Abflachung ist so einfach wie:

LINQ-Version

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

Nicht-LINQ-Version

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

Design-Entscheidungen

ich beschlossen:

• Verbieten eines Null-IEnumerable Abflachung, kann dies durch Entfernen Ausnahme Wurf geändert werden und:
  • Hinzufügen source = source.EmptyIfNull(); vor return in der ersten Version
  • Hinzufügen if (source != null) vor foreach in der 2. Version
• erlaubt durch den Wähler von einer Null-Sammlung Rückkehr - auf diese Weise ich die Verantwortung von dem Anrufer zu entfernen bin die Kinder Liste, um sicherzustellen, nicht leer ist, kann dies durch geändert werden:
  • .EmptyIfNull() in der ersten Version zu entfernen - beachten Sie, dass SelectMany wird scheitern, wenn null durch Selektor zurückgegeben
  • if (children == null) continue; in der zweiten Version zu entfernen - beachten Sie, dass foreach auf null IEnumerable Parameter fehlschlagen
• Lassen Sie Kinder mit .Where Klausel auf der Anruferseite oder innerhalb des Kinder Selektor Filterung , anstatt eine Kinder Filterselektor vorbei Parameter:
  • es wird nicht die Effizienz auswirken, da in beiden Versionen es eine verzögerte Aufruf
  • wäre es eine andere Logik mit dem Verfahren wird das Mischen und ich ziehe die Logik getrennt zu halten

Proben Verwendung

Ich bin mit dieser Erweiterung Methode in Light alle Steuerelemente auf dem Bildschirm zu erhalten:

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 4

Ist das nicht was [Select] [1] ist für die?

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

Answer 5

Hier ist eine modifizierte Jon Skeet Antwort mehr zu erlauben, als „eine Ebene“:

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:. Ich weiß nicht, C #

Das gleiche 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=" ")

Es druckt:

1 2 3 4 5 6 7 8 

Answer 6

Funktion:

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

Verbrauch:

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 7

Die SelectMany Erweiterungsmethode tut dies bereits.

  

Projiziert jedes Element einer Sequenz   ein IEnumerable <(Of <(T>)>) und   flacht die resultierenden Sequenzen in   eine Sequenz.

Answer 8

Da Ausbeute nicht in VB und LINQ bietet sowohl verzögerte Ausführung und eine kurze Syntax, können Sie auch.

<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 9

Ich hatte mir von Grund auf neu zu implementieren, da alle bereitgestellten Lösungen für den Fall, brechen würde es eine Schleife das heißt ein Kind, das seine Vorfahren verweist. Wenn Sie die gleichen Anforderungen wie meins haben einen Blick auf diese bitte nehmen (auch lassen Sie mich wissen, ob meine Lösung in irgendwelchen besonderen Umständen brechen würde):

Wie verwenden:

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

Code:

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 10

Okay, hier ist eine andere Version, die von etwa 3 Antworten oben kombiniert wird.

Recursive. Verwendet Ausbeute. Generisch. Optional Filterprädikat. Optionale Auswahlfunktion. Über so knapp wie ich es machen könnte.

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

Verbrauch:

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

Answer 11

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

Vielleicht so? Oder meinen Sie, dass es potentiell unendlich tief sein könnte?

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

Basicly, benötigen Sie einen Master IEnumerable haben, die außerhalb Ihrer rekursive Funktion ist, dann in Ihrem rekursive Funktion (Psuedo-Code)

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

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

Obwohl ich wirklich nicht sicher bin, was Sie von IEnumerable verschachtelten in einer IEnumerable meinen ... was in dem? Wie viele Verschachtelungsebenen? Was ist die letzte Art? offensichtlich mein Code nicht korrekt ist, aber ich hoffe, es wird dich zu denken.