使用LINQ的拓扑排序

我建议使用相同的IComparer接口,但编写扩展方法,以便将0解释为不相关。在部分排序中,如果元素a和b相等,那么它们的顺序就不重要了,就像wise一样,如果它们不相关,那么您只需要对它们定义了关系的元素进行排序。

下面是一个对偶数和奇数进行部分排序的示例:

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

这是我的优化和翻新版本 tehMick 's answer .

我所做的一个改变是 列表 为逻辑列表生成的值。为此,我有两个大小相同的数组。一个包含所有值,另一个包含标志,指示是否已生成每个值。这样,我就避免了必须调整 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--;
    }
}

嗯,我不确定这种处理方式是最好的方式,但我可能错了。

处理拓扑排序的典型方法是使用一个图,对于每个迭代,删除所有没有入站连接的节点,同时从这些节点中删除所有出站连接。删除的节点是迭代的输出。重复此操作,直到无法删除更多节点。

但是,为了首先获得这些连接,使用您的方法,您需要:

1. 一种方法(比较器),可以说“在此之前”,也可以说“没有这两个的信息”
2. 迭代所有组合,为比较器返回排序的所有组合创建连接。

换句话说,该方法的定义可能如下:

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

然后返回 null 当两个键没有决定性的答案时。

我正在考虑的问题是“迭代所有组合”部分。也许有更好的方法来处理这个问题,但我看不到。

我相信 Lasse V. Karlsen's answer 是在正确的轨道上,但我不喜欢隐藏比较方法(或者是一个独立的接口,它不能从 IComparable<T> )。

相反,我宁愿看到这样的东西:

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

这样,您仍然可以实现 IComparer<T> 可以在其他需要的地方使用 i比较程序<t> .

但是,它还要求您按照以下方式(类似于 i可比较<t> ):

• 空实例彼此不可比较。
• 0-这些实例相互比较。

• 0-x是一个可比较的键,但y不是。

• <0-y是一个可比较的键,但x不是。

当然,当将此实现传递给任何需要 i可比较<t> (应该注意的是,lasse v.karlsen的答案也不能解决这个问题),因为你所需要的不能用一个简单的比较方法来表示,它接受两个t的实例,并返回一个in t。

要完成这个解决方案,您必须提供一个自定义的orderby(以及thenby、orderbyDescending和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;            
    }
}

定义部分订单关系的接口:

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}

尊重部分秩序。

那很有趣。谢谢。

非常感谢大家,从埃里克·米克尔森的回答开始,我提出了我的版本,因为我更喜欢使用空值来表示没有关系,如拉塞尔诉卡尔森所说。

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