4

之间有什么区别

  • 严格/非严格排序，
  • 弱/非弱排序，以及
  • 部分/全部排序？
4

2 回答 2

6

设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  <  y和y  <  x在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 都是“最小元素”，因为没有比它更小的元素了。尽管如此，没有唯一的最小元素。

于 2013-02-18T14:14:23.933 回答
0

简单地说，严格的弱排序被定义为定义（可计算的）等价关系的排序。等价类按严格弱排序排序：严格弱排序是对等价类的严格排序。

部分排序（不是严格的弱排序）没有定义等价关系，因此任何使用“等价元素”概念的规范对于严格的弱排序都是没有意义的。所有 STL 关联容器在某些时候都使用这个概念，因此所有这些规范对于严格的弱排序都是没有意义的。

因为部分排序（不是严格的弱排序）没有定义任何严格的排序，所以您不能根据偏排序在常识中“对元素进行排序”（您所能做的只是具有较弱属性的“拓扑排序”） .

给定

  • 一个数学集S
  • <部分排序S
  • x一个值S

你可以定义一个分区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

一个序列根据< iff对序列中的每一个x进行排序，其中的元素L(x)首先出现在序列中，然后是 的元素I(x)，然后是 的元素G(x)。

当序列中出现在另一个元素之后的每个元素不小于时，一个序列是拓扑排序的。这是一个比排序更弱的约束。yxyx

证明 的每个元素L(x)都小于 的任何元素是微不足道的G(x)。L(x)的元素和 的元素I(x)之间，或 的元素I(x)和 的元素之间没有一般关系G(x)。但是，如果<是严格的弱关系，则比 的每个元素L(x)都小于 的任何元素I(x)，并且 的任何元素I(x)都小于 的任何元素G(x)。

If<是严格的弱关系，x<y则 的任何元素L(x) U I(x)小于任何元素I(y) U G(y)：不大于x的任何元素小于不小于 的任何元素y。这不适用于部分排序。

于 2013-06-16T10:19:59.767 回答