总序、弱序、偏序-完整定义

Question

总序、弱序、偏序-完整定义

language-agnosticstrict-weak-ordering

4

严格/非严格排序，强/非强排序以及部分/全序列有什么区别？

严格/非严格排序：在严格排序中，如果两个元素不能被比较，则它们是等效的。在非严格排序中，如果两个元素不能被比较，则它们可以被视为相等。
强/非强排序：在强排序中，所有元素都可以被比较。在非强排序中，一些元素可能无法比较。
部分/全序列：在部分排序中，某些元素可能无法比较。在全序列中，所有元素都可以比较。

- Johnny Pauling

维基百科的文章非常简洁。C++标准在[lib.alg.sorting]中也给出了一个很好的定义。你具体是哪方面感到困惑？ - Oliver Charlesworth

严格模式和非严格模式有什么区别？ - Johnny Pauling

1

http://cpp-next.com/archive/2010/02/order-i-say/ - Jerry Coffin

这与C++或算法无关。如果您不同意，请编辑您的问题（然后编辑标签）。 - Johannes Schaub - litb

2

@JerryCoffin，现在它在这里：http://web.archive.org/web/20120422220137/http://cpp-next.com/archive/2010/02/order-i-say/ - Dave Abrahams

2个回答

0

简而言之，严格弱序被定义为一种定义了（可计算的）等价关系的排序方式。等价类通过严格弱序进行排序：严格弱序是等价类的一个严格排序。

非严格弱序的偏序并不定义等价关系，因此在使用严格弱序的概念时，“等价元素”的任何规定都是没有意义的。所有的STL关联容器都在某个地方使用了这个概念，所以所有这些规定在使用严格弱序时都是没有意义的。

由于非严格弱序的偏序不定义任何严格排序，所以你不能按照偏序的常规意义对元素进行“排序”（你所能做的只是进行“拓扑排序”，其性质较弱）。

给定：

- 一个数学集合S - 集合S上的一个偏序< - S中的一个值x

你可以定义S的一个划分（S中的每个元素都在L（x）、I（x）或G（x）中）。

L(x) = { y in S | y<x }
I(x) = { y in S | not(y<x) and not(x<y) }
G(x) = { y in S | x<y }

 L(x) : set of elements less than x
 I(x) : set of elements incomparable with x
 G(x) : set of elements greater than x

如果对于序列中的每个x，L(x)的元素首先出现在序列中，然后是I(x)的元素，最后是G(x)的元素，则该序列按照<排序。

如果对于序列中的另一个元素y出现在元素x之后，y不小于x，则该序列是拓扑排序。这是比排序更弱的约束条件。

很容易证明L(x)的每个元素都小于G(x)的任何元素。L(x)的元素与I(x)的元素之间或I(x)的元素与G(x)的元素之间没有普遍关系。但是，如果<是严格的弱关系，则L(x)的每个元素都小于I(x)的任何元素，并且I(x)的任何元素都小于G(x)的任何元素。

如果<是一个严格的弱关系，并且x<y，那么L(x) U I(x)中的任何元素都小于I(y) U G(y)中的任何元素：任何不大于x的元素都小于任何不小于y的元素。这在部分排序中不成立。

- curiousguy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Kerrek SB · Accepted Answer

让X是一个集合。如果满足以下条件，则关系 < ⊆ X × X 是一个偏序关系：

对于所有的 x ∈ X，我们从来没有 x < x，
每当 x < y，我们从来没有 y < x，并且
每当 x < y 和 y < z，我们就有 x < z。

全序关系是具有附加属性的偏序排列，即对于任何两个 x 和 y，我们精确地有一个 x < y，或者 y < x，或者 x = y。

在我所知道的范围内，集合X上的弱排序是指具有附加属性的偏序排序 <，其中由等价类集X / ~诱导的排序是一个全序关系，其中 [x] = [y] ∈ X / ~ 当且仅当在X中不成立x < y，也不成立 y < x。

换句话说，在偏序排列中，可以比较一些元素，并且如果它们可以比较，则排序是一致的。具有偏序关系的示例：

集合X的适当子集，其中 A < B 意味着 A ⊊ B。
使用 a < b 表示“a整除b”的自然数。
C++中的模板特化。

总排序是其中所有元素一起形成单个一致的排序。 弱排序是一种总排序，如果你愿意将几个元素归为一类，并将它们视为排序目的的等效元素。

术语“严格”是指使用“<”作为定义关系，而不是“≤”。您可以看到如何轻松地重新编写所有定义，以≤为例，例如，在部分排序中，我们始终具有x ≤ x等。

以下是两个示例，都是C++模板特化。当然，两者都是部分排序的，但第一个也是完全排序的。

示例#1：

template <typename T> struct Foo {};               // A1
template <typename U> struct Foo<U*> {};           // A2
template <> struct Foo<int*> {};                   // A3

这些专业化领域按照完全有序的方式排列，A3 < A2 < A1，其中"<"表示"比...更专业化"。 示例 #2:

template <typename T1, typename T2> struct Bar {}; // B1
template <typename U> struct Bar<int, U> {};       // B2a
template <typename V> struct Bar<V, int> {};       // B2b
template <> struct Bar<int, int> {};               // B3

这次，我们有B3 < B2b < B1和B3 < B2a < B1，但B2a和B2b是不可比较的。

在C++中，这样表现出来：如果未定义专业化B3，则尝试实例化Bar<int，int>将导致编译器错误，因为没有明确的“最专业”的专业化。

偏序集可以有许多“最小”元素和“最大”元素，因为这些概念只能谈论可比较的元素。在B1、B2a和B2b中，B2a和B2b都是“最小元素”，因为没有更小的元素。尽管如此，没有唯一的最小元素。