Aplatissement récursif de la liste

Question

Je pourrais probablement écrire cela moi-même, mais la façon spécifique que j'essaie de faire est de me désarçonner. J'essaie d'écrire une méthode d'extension générique semblable aux autres méthodes introduites dans .NET 3.5 qui prend un IEnumerable imbriqué d'IEnumerables (et ainsi de suite) et l'aplatit en un IEnumerable. Quelqu'un a des idées?

Plus précisément, j'ai des problèmes avec la syntaxe de la méthode d'extension elle-même pour pouvoir travailler sur un algorithme d'aplatissement.

Answer 1

Hmm ... Je ne suis pas sûr de savoir exactement ce que vous voulez ici, mais voici un & "un niveau &"; 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;
        }
    }
}

Si ce n'est pas ce que vous voulez, pouvez-vous fournir la signature de ce que vous voulez? Si vous n'avez pas besoin d'un formulaire générique et que vous voulez simplement faire ce que font les constructeurs LINQ to XML, c'est assez simple, bien que l'utilisation récursive de blocs d'itérateur soit relativement inefficace. Quelque chose comme:

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

Notez que cela traitera une chaîne de caractères comme une séquence de caractères. Toutefois, vous souhaiterez peut-être que les chaînes de casse soient des éléments individuels au lieu de les aplatir, selon votre cas d'utilisation.

Est-ce que cela vous aide?

Answer 2

Voici une extension qui pourrait aider. Il traversera tous les nœuds de votre hiérarchie d'objets et choisira ceux qui correspondent à un critère. Cela suppose que chaque objet de votre hiérarchie possède une propriété de collection contenant ses objets enfants.

Voici l'extension:

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

Exemples (tests unitaires):

Nous avons d’abord besoin d’un objet et d’une hiérarchie d’objets imbriqués.

Une classe de noeud 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);
  }
}

Et une méthode pour obtenir une hiérarchie profonde à 3 niveaux de nœuds

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

Premier test: aplatir la hiérarchie, pas de filtrage

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

Cela montrera:

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

Second test: obtenez une liste de noeuds dotés d'un NodeId de numéro pair

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

Cela montrera:

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

Answer 3

Je pensais partager un exemple complet avec la gestion des erreurs et une approche à logique unique.

L'aplatissement récursif est aussi simple que:

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

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

Décisions de conception

J'ai décidé de:

• n'autorise pas l'aplatissement d'une valeur nulle IEnumerable; vous pouvez le modifier en supprimant le lancement d'exceptions et:
  • ajout de source = source.EmptyIfNull(); avant return dans la 1ère version
  • ajouter if (source != null) avant foreach dans la 2e version
• autoriser le sélecteur à renvoyer une collection null. De cette façon, je retire la responsabilité de l'appelant pour m'assurer que la liste des enfants n'est pas vide. Cela peut être modifié de la manière suivante:
  • supprimer .EmptyIfNull() dans la première version - notez que SelectMany échouera si la valeur null est renvoyée par le sélecteur
  • supprimer if (children == null) continue; dans la deuxième version - notez que .Where échouera avec un paramètre null <=>
• permet de filtrer les enfants avec la clause <=> du côté de l'appelant ou dans le sélecteur d'enfants plutôt que de transmettre un paramètre de sélecteur de filtre d'enfants :
  • cela n’affectera pas l’efficacité car dans les deux versions, il s’agit d’un appel différé
  • ce serait mélanger une autre logique avec la méthode et je préfère garder la logique séparée

Exemple d'utilisation

J'utilise cette méthode d'extension dans LightSwitch pour obtenir tous les contrôles à l'écran:

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

N’est-ce pas à quoi sert [SelectMany] [1]?

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

Answer 5

Voici une réponse de Jon Skeet modifiée pour autoriser plus de " niveau "

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: je ne connais pas le c #.

Idem 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=" ")

Il imprime:

1 2 3 4 5 6 7 8 

Answer 6

Fonction:

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

Utilisation:

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

L'extension SelectMany La méthode le fait déjà.

  

Projette chaque élément d'une séquence sur   un IEnumerable < (Of < (T >) >) et   aplatit les séquences résultantes en   une séquence.

Answer 8

Le rendement n'étant pas disponible dans VB et LINQ fournissant à la fois une exécution différée et une syntaxe concise, vous pouvez également utiliser.

<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

J'ai dû implémenter la mienne à partir de zéro, car toutes les solutions proposées se briseraient au cas où il y aurait une boucle, c'est-à-dire un enfant qui pointe vers son ancêtre. Si vous avez les mêmes exigences que la mienne, jetez-y un coup d'œil (laissez-moi également savoir si ma solution se briserait dans des circonstances particulières):

Comment utiliser:

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

Ok, voici une autre version qui est combinée à partir de 3 réponses ci-dessus.

Récursif. Utilise le rendement. Générique. Prédicat de filtre facultatif. Fonction de sélection facultative. Aussi concis que possible.

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

Utilisation:

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

Peut-être comme ça? Ou voulez-vous dire que cela pourrait être potentiellement très profond?

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

En gros, vous devez avoir un maître IENumerable en dehors de votre fonction récursive, puis dans votre fonction récursive (code Psuedo)

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

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

Bien que je ne sois vraiment pas sûr de ce que vous entendez par IEnumerable imbriqué dans un IEnumerable ... que contient-il? Combien de niveaux de nidification? Quel est le type final? évidemment, mon code n'est pas correct, mais j'espère que cela vous fera réfléchir.