الفرز الطوبولوجي باستخدام LINQ

Question

لدي قائمة بالعناصر التي لديها ملف علاقة ترتيب جزئي, ، أنا. هـ ، يمكن اعتبار القائمة أ مجموعة مرتبة جزئيا. أريد فرز هذه القائمة بنفس الطريقة التي في هذا سؤال. كما أجاب بشكل صحيح هناك ، يُعرف هذا باسم الفرز الطوبولوجي.

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

لقد حاولت بالفعل استخدام OrderBy طريقة التمديد ، لكنني متأكد تمامًا من أنها غير قادرة على إجراء فرز طوبولوجي. المشكلة هي أن IComparer<TKey> الواجهة غير قادرة على تمثيل ترتيب جزئي. هذا يحدث لأن ال Compare يمكن أن تعود الطريقة بشكل أساسي 3 أنواع من القيم: صفر, نفي, ، و إيجابي, ، المعنى متساوون, اقل من, ، و IS-greater-then, ، على التوالى. سيكون حل العمل ممكنًا فقط إذا كانت هناك طريقة للعودة غير مرتبطة.

من وجهة نظري المتحيزة ، قد تتألف الإجابة التي أبحث عنها IPartialOrderComparer<T> واجهة وطريقة تمديد مثل هذا:

public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(
    this IEnumerable<TSource> source,
    Func<TSource, TKey> keySelector,
    IPartialOrderComparer<TKey> comparer
);

كيف سيتم تنفيذ هذا؟ كيف يمكن لل IPartialOrderComparer<T> الواجهة ستبدو؟ هل تنصح بنهج مختلف؟ أنا حريص على رؤيته. ربما هناك طريقة أجمل لتمثيل النظام الجزئي ، لا أعرف.

Answer 1

أود أن أقترح استخدام واجهة icomparer نفسها ، ولكن كتابة طريقة التمديد وذلك لتفسير 0 على أنه غير مرتبط. في ترتيب جزئي ، إذا كانت العناصران A و B متساوية في ترتيبها ، فهذا لا يهم ، مثل الحكم إذا كانت غير ذات صلة - عليك فقط أن تطلبها فيما يتعلق بالعناصر التي حددها العلاقات معها.

فيما يلي مثال يقوم بترتيب جزئي للأعداد الصحيحة والخبراء:

namespace PartialOrdering
{
    public static class Enumerable
    {
        public static IEnumerable<TSource> PartialOrderBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer)
        {
            List<TSource> list = new List<TSource>(source);
            while (list.Count > 0)
            {
                TSource minimum = default(TSource);
                TKey minimumKey = default(TKey);
                foreach (TSource s in list)
                {
                    TKey k = keySelector(s);
                    minimum = s;
                    minimumKey = k;
                    break;
                }
                foreach (TSource s in list)
                {
                    TKey k = keySelector(s);
                    if (comparer.Compare(k, minimumKey) < 0)
                    {
                        minimum = s;
                        minimumKey = k;
                    }
                }
                yield return minimum;
                list.Remove(minimum);
            }
            yield break;
        }

    }
    public class EvenOddPartialOrdering : IComparer<int>
    {
        public int Compare(int a, int b)
        {
            if (a % 2 != b % 2)
                return 0;
            else if (a < b)
                return -1;
            else if (a > b)
                return 1;
            else return 0; //equal
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            IEnumerable<Int32> integers = new List<int> { 8, 4, 5, 7, 10, 3 };
            integers = integers.PartialOrderBy<Int32, Int32>(new Func<Int32, Int32>(delegate(int i) { return i; }), new EvenOddPartialOrdering());
        }
    }
}

النتيجة: 4 ، 8 ، 3 ، 5 ، 7 ، 10

Answer 2

هذا هو نسختي المحسنة والتجديد من tehmickإجابة.

تغيير واحد قمت به هو استبدال حقيقي قائمة من القيم التي تركت للعائد للحصول على قائمة منطقية. لهذا ، لدي صفيفان الحجم من نفس الحجم. واحد لديه كل القيم ، والبعض الآخر يحتوي على أعلام تخبر ما إذا كانت كل قيمة قد تم تقديمها. بهذه الطريقة ، أتجنب تكلفة الاضطرار إلى تغيير حجم حقيقي List<Key>.

أحد التغييرات الأخرى هو أنني أقرأ جميع المفاتيح مرة واحدة فقط في بداية التكرار. لأسباب لا أستطيع تذكرها الآن (ربما كانت غريزتي فقط) لا أحب فكرة الاتصال keySelector تعمل عدة مرات.

كانت اللمسات الأخيرة هي التحقق من صحة المعلمة ، وحمل إضافي يستخدم مقارنًا ضمنيًا. آمل أن يكون الكود قابلاً للقراءة بما فيه الكفاية. تحقق من ذلك.

public static IEnumerable<TSource> PartialOrderBy<TSource, TKey>(
    this IEnumerable<TSource> source,
    Func<TSource, TKey> keySelector)
{
    return PartialOrderBy(source, keySelector, null);
}

public static IEnumerable<TSource> PartialOrderBy<TSource, TKey>(
    this IEnumerable<TSource> source,
    Func<TSource, TKey> keySelector,
    IComparer<TKey> comparer)
{
    if (source == null) throw new ArgumentNullException("source");
    if (keySelector == null) throw new ArgumentNullException("keySelector");
    if (comparer == null) comparer = (IComparer<TKey>)Comparer<TKey>.Default;

    return PartialOrderByIterator(source, keySelector, comparer);
}

private static IEnumerable<TSource> PartialOrderByIterator<TSource, TKey>(
    IEnumerable<TSource> source,
    Func<TSource, TKey> keySelector,
    IComparer<TKey> comparer)
{
    var values = source.ToArray();
    var keys = values.Select(keySelector).ToArray();
    int count = values.Length;
    var notYieldedIndexes = System.Linq.Enumerable.Range(0, count).ToArray();
    int valuesToGo = count;

    while (valuesToGo > 0)
    {
        //Start with first value not yielded yet
        int minIndex = notYieldedIndexes.First( i => i >= 0);

        //Find minimum value amongst the values not yielded yet
        for (int i=0; i<count; i++)
        if (notYieldedIndexes[i] >= 0)
        if (comparer.Compare(keys[i], keys[minIndex]) < 0) {
            minIndex = i;
        }

        //Yield minimum value and mark it as yielded
        yield return values[minIndex];
        notYieldedIndexes[minIndex] = -1;
        valuesToGo--;
    }
}

Answer 3

حسنًا ، لست متأكدًا من أن طريقة التعامل معها هي أفضل طريقة ، لكنني قد أكون مخطئًا.

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

ومع ذلك ، من أجل الحصول على هذه الاتصالات في المقام الأول ، مع طريقتك ، ستحتاج:

1. طريقة (مقارنتك) يمكن أن تقول "هذا قبل ذلك" ولكن أيضًا "لا توجد معلومات لهذين الاثنين"
2. تكرار جميع المجموعات ، مما يؤدي إلى إنشاء اتصالات لجميع المجموعات التي يعيد المقارن طلبًا إليها.

بمعنى آخر ، من المحتمل أن يتم تعريف الطريقة على هذا النحو:

public Int32? Compare(TKey a, TKey b) { ... }

ثم العودة null عندما لا يكون لديه إجابة قاطعة لمفتاحين.

المشكلة التي أفكر فيها هي جزء "تكرار جميع المجموعات". ربما هناك طريقة أفضل للتعامل مع هذا ، لكنني لا أراها.

Answer 4

أعتقد أن إجابة Lasse V. Karlsen موجود على المسار الصحيح ، لكني لا أحب إخفاء طريقة المقارنة (أو واجهة منفصلة لهذه المسألة التي لا تمتد من IComparable<T>).

بدلاً من ذلك ، أفضل رؤية شيء كهذا:

public interface IPartialOrderComparer<T> : IComparer<T>
{
    int? InstancesAreComparable(T x, T y);
}

بهذه الطريقة ، لا يزال لديك تنفيذ IComparer<T> التي يمكن استخدامها في أماكن أخرى تتطلب IComparer<T>.

ومع ذلك ، فإنه يتطلب منك أيضًا الإشارة إلى علاقة مثيلات T ببعضها البعض مع قيمة الإرجاع بالطريقة التالية (على غرار IComparable<T>):

• NULL - حالات لا يمكن مقارنتها ببعضها البعض.
• 0 - الحالات مماثلة لبعضها البعض.

• 0 - X هو مفتاح مماثل ، ولكن Y ليس كذلك.

• <0 - y هو مفتاح مماثل ، لكن X ليس كذلك.

بالطبع ، لن تحصل على طلب جزئي عند تمرير تنفيذ هذا إلى أي شيء يتوقع IComparable<T> (وتجدر الإشارة إلى أن إجابة Lasse V. Karlsen لا تحل هذا أيضًا) لأن ما تحتاجه لا يمكن تمثيله بطريقة بسيطة للمقارنة التي تأخذ حالتين من T وإرجاع int.

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

public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(      
    this IEnumerable<TSource> source,      
    Func<TSource, TKey> keySelector,      
    IPartialOrderComparer<TKey> comparer)
{
    return Enumerable.OrderBy(source, keySelector,
        new PartialOrderComparer(comparer);
}

internal class PartialOrderComparer<T> : IComparer<T>
{
    internal PartialOrderComparer(IPartialOrderComparer<T> 
        partialOrderComparer)
    {
        this.partialOrderComparer = partialOrderComparer;
    }

    private readonly IPartialOrderComparer<T> partialOrderComparer;

    public int Compare(T x, T y)
    {
        // See if the items are comparable.
        int? comparable = partialOrderComparable.
            InstancesAreComparable(x, y);

        // If they are not comparable (null), then return
        // 0, they are equal and it doesn't matter
        // what order they are returned in.
        // Remember that this only to determine the
        // values in relation to each other, so it's
        // ok to say they are equal.
        if (comparable == null) return 0;

        // If the value is 0, they are comparable, return
        // the result of that.
        if (comparable.Value == 0) return partialOrderComparer.Compare(x, y);

        // One or the other is uncomparable.
        // Return the negative of the value.
        // If comparable is negative, then y is comparable
        // and x is not.  Therefore, x should be greater than y (think
        // of it in terms of coming later in the list after
        // the ordered elements).
        return -comparable.Value;            
    }
}

Answer 5

واجهة لتحديد علاقة الطلب الجزئي:

interface IPartialComparer<T> {
    int? Compare(T x, T y);
}

Compare يجب أن تعود -1 إذا x < y, 0 إذا x = y, 1 إذا y < x و null إذا x و y غير قابلة للمقارنة.

هدفنا هو إعادة ترتيب العناصر بالترتيب الجزئي الذي يحترم التعداد. وهذا هو ، نحن نبحث عن تسلسل e_1, e_2, e_3, ..., e_n من العناصر في الترتيب الجزئي مثل إذا i <= j و e_i مماثلة ل e_j ومن بعد e_i <= e_j. سأفعل هذا باستخدام بحث عمق الأول.

الفئة التي تنفذ النوع الطوبولوجي باستخدام بحث العمق الأول:

class TopologicalSorter {
    class DepthFirstSearch<TElement, TKey> {
        readonly IEnumerable<TElement> _elements;
        readonly Func<TElement, TKey> _selector;
        readonly IPartialComparer<TKey> _comparer;
        HashSet<TElement> _visited;
        Dictionary<TElement, TKey> _keys;
        List<TElement> _sorted;

        public DepthFirstSearch(
            IEnumerable<TElement> elements,
            Func<TElement, TKey> selector,
            IPartialComparer<TKey> comparer
        ) {
            _elements = elements;
            _selector = selector;
            _comparer = comparer;
            var referenceComparer = new ReferenceEqualityComparer<TElement>();
            _visited = new HashSet<TElement>(referenceComparer);
            _keys = elements.ToDictionary(
                e => e,
                e => _selector(e), 
                referenceComparer
            );
            _sorted = new List<TElement>();
        }

        public IEnumerable<TElement> VisitAll() {
            foreach (var element in _elements) {
                Visit(element);
            }
            return _sorted;
        }

        void Visit(TElement element) {
            if (!_visited.Contains(element)) {
                _visited.Add(element);
                var predecessors = _elements.Where(
                    e => _comparer.Compare(_keys[e], _keys[element]) < 0
                );
                foreach (var e in predecessors) {
                    Visit(e);
                }
                _sorted.Add(element);
            }
        }
    }

    public IEnumerable<TElement> ToplogicalSort<TElement, TKey>(
        IEnumerable<TElement> elements,
        Func<TElement, TKey> selector, IPartialComparer<TKey> comparer
    ) {
        var search = new DepthFirstSearch<TElement, TKey>(
            elements,
            selector,
            comparer
        );
        return search.VisitAll();
    }
}

فئة المساعدة اللازمة لوضع علامات على ذلك كما تمت زيارته أثناء إجراء البحث الأول في العمق:

class ReferenceEqualityComparer<T> : IEqualityComparer<T> {
    public bool Equals(T x, T y) {
        return Object.ReferenceEquals(x, y);
    }

    public int GetHashCode(T obj) {
        return obj.GetHashCode();
    }
}

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

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

public void Visit(TElement element) {
    // if we haven't already visited the element
    if (!_visited.Contains(element)) {
        // mark it as visited
        _visited.Add(element);
        var predecessors = _elements.Where(
            e => _comparer.Compare(_keys[e], _keys[element]) < 0
        );
        // visit its predecessors
        foreach (var e in predecessors) {
            Visit(e);
        }
        // add it to the ordering
        // at this point we are certain that
        // its predecessors are already in the ordering
        _sorted.Add(element);
    }
}

على سبيل المثال ، فكر في الترتيب الجزئي المحدد على مجموعات فرعية من {1, 2, 3} أين X < Y إذا X هي مجموعة فرعية من Y. أقوم بتنفيذ هذا على النحو التالي:

public class SetComparer : IPartialComparer<HashSet<int>> {
    public int? Compare(HashSet<int> x, HashSet<int> y) {
        bool xSubsety = x.All(i => y.Contains(i));
        bool ySubsetx = y.All(i => x.Contains(i));
        if (xSubsety) {
            if (ySubsetx) {
                return 0;
            }
            return -1;
        }
        if (ySubsetx) {
            return 1;
        }
        return null;
    }
}

ثم مع sets يُعرّف بأنه قائمة المجموعات الفرعية {1, 2, 3}

List<HashSet<int>> sets = new List<HashSet<int>>() {
    new HashSet<int>(new List<int>() {}),
    new HashSet<int>(new List<int>() { 1, 2, 3 }),
    new HashSet<int>(new List<int>() { 2 }),
    new HashSet<int>(new List<int>() { 2, 3}),
    new HashSet<int>(new List<int>() { 3 }),
    new HashSet<int>(new List<int>() { 1, 3 }),
    new HashSet<int>(new List<int>() { 1, 2 }),
    new HashSet<int>(new List<int>() { 1 })
};
TopologicalSorter s = new TopologicalSorter();
var sorted = s.ToplogicalSort(sets, set => set, new SetComparer());

هذا يؤدي إلى الطلب:

{}, {2}, {3}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}

الذي يحترم النظام الجزئي.

كان هذا الكثير من المرح. شكرًا.

Answer 6

شكرًا جزيلاً للجميع ، بدءًا من إجابة Eric Mickelsen لقد توصلت إلى روايتي لأنني أفضل استخدام القيم الخالية للإشارة إلى عدم وجود علاقة كما قال Lasse V. Karlsen.

public static IEnumerable<TSource> PartialOrderBy<TSource>(
        this IEnumerable<TSource> source,            
        IPartialEqualityComparer<TSource> comparer)
    {
        if (source == null) throw new ArgumentNullException("source");
        if (comparer == null) throw new ArgumentNullException("comparer");


        var set = new HashSet<TSource>(source);
        while (!set.IsEmpty())
        {
            TSource minimum = set.First();                

            foreach (TSource s in set)
            {                    
                var comparison = comparer.Compare(s, minimum);
                if (!comparison.HasValue) continue;
                if (comparison.Value <= 0)
                {
                    minimum = s;                        
                }
            }
            yield return minimum;
            set.Remove(minimum);
        }
    }

public static IEnumerable<TSource> PartialOrderBy<TSource>(
       this IEnumerable<TSource> source,
       Func<TSource, TSource, int?> comparer)
    {
        return PartialOrderBy(source, new PartialEqualityComparer<TSource>(comparer));
    }

ثم لدي الواجهة التالية للمقارنة

public interface IPartialEqualityComparer<T>
{
    int? Compare(T x, T y);
}

وهذه فئة المساعد

internal class PartialEqualityComparer<TSource> : IPartialEqualityComparer<TSource>
{
    private Func<TSource, TSource, int?> comparer;

    public PartialEqualityComparer(Func<TSource, TSource, int?> comparer)
    {
        this.comparer = comparer;
    }

    public int? Compare(TSource x, TSource y)
    {
        return comparer(x,y);
    }
}

يسمح ذلك بتجميل الاستخدام قليلاً حتى تبدو اختباراتي كما يلي

 var data = new int[] { 8,7,6,5,4,3,2,1,0 };
 var partiallyOrdered = data.PartialOrderBy((x, y) =>
     {
        if (x % 2 == 0 && y % 2 != 0) return null;
        return x.CompareTo(y);
     });