تسطيح القائمة العودية

Question

ربما أستطيع أن أكتب هذا بنفسي، لكن الطريقة المحددة التي أحاول إنجازها تزعجني.أحاول كتابة طريقة تمديد عامة مشابهة لتلك التي تم تقديمها في .NET 3.5 والتي ستأخذ IEnumerable المتداخل من IEnumerables (وهكذا) وتسويته في IEnumerable واحد.هل لدي احد اى افكار؟

على وجه التحديد، أواجه مشكلة في بناء جملة طريقة الامتداد نفسها حتى أتمكن من العمل على خوارزمية التسوية.

Answer 1

همم...لست متأكد بالضبط ما تريده هنا، ولكن إليك خيار "المستوى الواحد":

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

إذا لم يكن هذا ما تريده، هل يمكنك تقديم التوقيع على ما تريده؟إذا لم تكن بحاجة إلى نموذج عام، وتريد فقط القيام بالشيء الذي تفعله مُنشئات LINQ إلى XML، فهذا بسيط إلى حد معقول - على الرغم من أن الاستخدام العودي للكتل المكررة غير فعال نسبيًا.شيء مثل:

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

لاحظ أن هذا سيعامل السلسلة على أنها سلسلة من الأحرف، ومع ذلك - قد ترغب في جعل السلاسل ذات الحالة الخاصة عناصر فردية بدلاً من تسطيحها، اعتمادًا على حالة الاستخدام الخاصة بك.

هل هذا يساعد؟

Answer 2

إليك امتدادًا قد يساعدك.سوف يجتاز جميع العقد في التسلسل الهرمي للكائنات ويختار تلك التي تطابق المعايير.يفترض أن كل كائن في التسلسل الهرمي الخاص بك لديه خاصية جمع الذي يحمل كائناته الفرعية.

وهنا التمديد:

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

أمثلة (اختبارات الوحدة):

نحتاج أولاً إلى كائن وتسلسل هرمي للكائنات المتداخلة.

فئة عقدة بسيطة

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

وطريقة للحصول على تسلسل هرمي عميق مكون من 3 مستويات للعقد

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

الاختبار الأول:تسوية التسلسل الهرمي، بدون تصفية

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

سيظهر هذا:

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

الاختبار الثاني:احصل على قائمة بالعقد التي تحتوي على NodeId ذات أرقام زوجية

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

سيظهر هذا:

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

Answer 3

اعتقدت أنني سأشارك مثالًا كاملاً مع معالجة الأخطاء ونهج المنطق الواحد.

التسطيح العودي بسيط مثل:

نسخة لينك

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

نسخة غير 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;
            }
        }
    }
}

قرارات التصميم

قررت أن:

• عدم السماح بتسوية قيمة خالية IEnumerable, ، يمكن تغيير ذلك عن طريق إزالة رمي الاستثناءات و:
  • إضافة source = source.EmptyIfNull(); قبل return في الإصدار الأول
  • إضافة if (source != null) قبل foreach في النسخة الثانية
• السماح بإرجاع مجموعة فارغة بواسطة المحدد - وبهذه الطريقة أقوم بإزالة المسؤولية من المتصل للتأكد من أن قائمة الأطفال ليست فارغة، ويمكن تغيير ذلك عن طريق:
  • إزالة .EmptyIfNull() في النسخة الأولى - لاحظ ذلك SelectMany سوف تفشل إذا تم إرجاع null بواسطة المحدد
  • إزالة if (children == null) continue; في الإصدار الثاني - لاحظ ذلك foreach سوف تفشل على فارغة IEnumerable معامل
• السماح بتصفية الأطفال مع .Where جملة على جانب المتصل أو داخل محدد الأطفال بدلا من تمرير أ محدد مرشح الأطفال معامل:
  • لن يؤثر ذلك على الكفاءة لأنه في كلا الإصدارين يكون مكالمة مؤجلة
  • سيكون خلط منطق آخر مع الطريقة وأفضل إبقاء المنطق منفصلاً

استخدام العينة

أنا أستخدم طريقة الامتداد هذه في LightSwitch للحصول على كافة عناصر التحكم على الشاشة:

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

أليس هذا هو الغرض من [SelectMany] [1]؟

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

Answer 5

هنا تعديل إجابة جون سكيت للسماح بأكثر من "مستوى واحد":

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

تنصل:لا أعرف لغة C#.

نفس الشيء في بايثون:

#!/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=" ")

يطبع:

1 2 3 4 5 6 7 8 

Answer 6

وظيفة:

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

الاستخدام:

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

ال SelectMany طريقة التمديد تفعل ذلك بالفعل.

مشاريع كل عنصر من عناصر التسلسل إلى ienumerable <(من <(t>)>) ويشوي التسلسلات الناتجة في تسلسل واحد.

Answer 8

نظرًا لأن العائد غير متوفر في VB ويوفر LINQ كلاً من التنفيذ المؤجل وبناء الجملة الموجز، يمكنك أيضًا استخدامه.

<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

اضطررت إلى تنفيذ حلولي من الصفر لأن جميع الحلول المقدمة ستتعطل في حالة وجود حلقة، على سبيل المثال.طفل يشير إلى جده.إذا كان لديك نفس متطلباتي، فيرجى إلقاء نظرة على هذا (أخبرني أيضًا إذا كان الحل الخاص بي سيتعطل في أي ظروف خاصة):

كيف تستعمل:

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

شفرة:

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

حسنًا، إليك إصدار آخر تم دمجه من حوالي 3 إجابات أعلاه.

العودية.يستخدم العائد.نوعي.المسند مرشح اختياري.وظيفة الاختيار الاختيارية.حول موجزة بقدر ما أستطيع أن أفعل ذلك.

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

الاستخدام:

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

ربما مثل هذا؟أم أنك تقصد أنه من المحتمل أن يكون عميقًا إلى ما لا نهاية؟

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

في الأساس، تحتاج إلى أن يكون لديك IENumerable رئيسي خارج وظيفتك العودية، ثم في وظيفتك العودية (الرمز الزائف)

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

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

على الرغم من أنني لست متأكدًا حقًا مما تقصده بـ IEnumerable المتداخل في IEnumerable... ماذا يوجد داخل ذلك؟كم عدد مستويات التعشيش؟ما هو النوع النهائي؟من الواضح أن الكود الخاص بي ليس صحيحًا، ولكن أتمنى أن يجعلك تفكر.