定义偏序关系的接口:
interface IPartialComparer<T> {
int? Compare(T x, T y);
}
Compare
应该返回 -1
如果 x < y
,0
如果 x = y
,1
如果 y < x
,如果 x
和 y
不可比,则返回 null
。
我们的目标是返回一个元素序列,该序列尊重枚举中的偏序。也就是说,我们寻求一个偏序中元素的序列 e_1, e_2, e_3, ..., e_n
,使得如果 i <= j
并且 e_i
可比于 e_j
,则 e_i <= e_j
。我将使用深度优先搜索来实现这一点。
实现使用深度优先搜索的拓扑排序的类:
class TopologicalSorter
public IEnumerable<TElement> VisitAll()
return _sorted;
}
void Visit(TElement element)
_sorted.Add(element);
}
}
}
public IEnumerable<TElement> ToplogicalSort<TElement, TKey>(
IEnumerable<TElement> elements,
Func<TElement, TKey> selector, IPartialComparer<TKey> comparer
)
}
需要一个辅助类来在进行深度优先搜索时标记节点为已访问:
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
,但一旦我们到达这个点,这很容易做到。
该算法通过对元素进行深度优先搜索来工作,如果我们已经将所有前驱元素添加到排序中(由算法中的_sorted
表示),则将元素e
添加到线性排序中。因此,对于每个元素e
,如果我们还没有访问它,请访问它的前驱,然后添加e
。因此,这是算法的核心:
public 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);
}
}
举个例子,考虑在集合{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;
}
}
然后,将{1, 2, 3}
的子集列表定义为sets
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}
尊重部分顺序。
真是太有趣了。谢谢。
default
可能会隐藏一些错误。例如,default(int)
是零,而它几乎不是最小的 int 值。你试过负值吗?无论如何,我明天早上会尝试一下。 - jpbochi