使用 LINQ 进行拓扑排序
-
22-09-2019 - |
题
我有一个项目列表,其中包含 偏序关系, , 我。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>
界面会是什么样子?您会推荐一种不同的方法吗?我很想看到它。也许有更好的方法来表示部分顺序,我不知道。
解决方案
我建议使用相同的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
其他提示
这是我的优化和翻新版本 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--;
}
}
好吧,我不确定这种处理方式是最好的方式,但我可能是错的。
处理拓扑排序的典型方法是使用图,并且对于每次迭代,删除所有没有入站连接的节点,并同时删除从这些节点出站的所有连接。删除的节点是迭代的输出。重复此操作,直到无法删除更多节点。
但是,为了首先使用您的方法获得这些连接,您需要:
- 一种方法(你的比较器)可以说“这个在那之前”,但也可以说“没有这两个的信息”
- 迭代所有组合,为比较器返回排序的所有组合创建连接。
换句话说,该方法可能会这样定义:
public Int32? Compare(TKey a, TKey b) { ... }
然后返回 null
当它没有两个密钥的结论性答案时。
我正在考虑的问题是“迭代所有组合”部分。也许有更好的方法来处理这个问题,但我没有看到。
我相信 拉塞 V.卡尔森的回答 是在正确的轨道上,但我不喜欢隐藏 Compare 方法(或一个单独的接口,它不从 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 的答案也没有解决这个问题),因为您需要的内容无法用简单的 Compare 方法表示,该方法接受 T 的两个实例并返回 int 。
要完成该解决方案,您必须提供一个自定义 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();
}
}
需要为已访问而做深度优先搜索标记节点Helper类:
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}
,尊重偏序。
这是一个很大的乐趣。感谢。
非常感谢大家,埃里克Mickelsen的回答[我已开始与我的版本上来,因为我更喜欢使用空值来表示作为拉塞五卡尔森说没有关系。
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);
});