.net - 使用 LINQ 进行拓扑排序

Question

我有一个包含 partial order relation 的项目列表， 我。 e，列表可以认为是partially ordered set 。我想以与此 question 相同的方式对此列表进行排序。正如那里正确回答的那样，这被称为 topological sorting .

有一个相当简单的已知算法可以解决这个问题。我想要一个类似 LINQ 的实现。

我已经尝试使用OrderBy扩展方法，但我很确定它无法进行拓扑排序。问题是IComparer<TKey>接口(interface)无法表示偏序。发生这种情况是因为 Compare方法基本上可以返回 3 种值:零、负和正，意思是等于、<分别是strong>小于和大于。只有存在返回不相关的方法，才可能有可行的解决方案。

从我的偏见来看，我正在寻找的答案可能由IPartialOrderComparer<T>组成。接口(interface)和扩展方法如下:

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

这将如何实现？ IPartialOrderComparer<T>如何界面会是什么样子？您会推荐一种不同的方法吗？我很想看到它。也许有更好的方法来表示部分顺序，我不知道。

Answer 1

我建议使用相同的 IComparer 接口(interface)，但编写扩展方法以便将 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