使用LINQ进行拓扑排序

Question

我有一个具有部分订单关系的项目列表,i.e,该列表可以被认为是部分有序的集合.我想以与此问题相同的方式对此列表进行排序.正如那里正确回答的那样,这被称为拓扑排序.

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

我已经尝试使用OrderBy扩展方法,但我很确定它无法进行拓扑排序.问题是IComparer<TKey>界面无法表示部分订单.之所以会发生这种情况,是因为该Compare方法基本上可以返回3种值:零,负和正,意味着 分别等于,小于,然后大于.只有返回无关的方法才能实现有效的解决方案.

从我偏见的角度来看,我正在寻找的答案可能是由一个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--;
    }
}