问题标签 [partial-ordering]

我有一个包含三列的表username：followerCount和CreateDate。

表中有大约 110000 个用户，我试图显示按followerCount. 我这样做：

因此，对于第二页，我从第一页通过最后followerCount一页，然后收到下一页，依此类推。

但是表中有些用户的关注者数量相同。例如有 250 个用户有 5000 个关注者。因此，当我进行分页时，我无法正确获取下一页，因为有更多用户拥有 5000 个关注者。

例如，我在第 9 页，最后一个用户有 5001 个关注者，我将 5001 传递给存储过程，我得到了 50 个拥有 5000 个用户的用户。但是还有 200 个用户，当我将这一次 5000（上一个分页中的最后一个数字）再次传递给我的存储过程时，它将跳过所有其他用户并为我带来 4xxx 个关注者的用户。

我如何才能带来拥有相同数量关注者的正确用户？

更正：我为此目的使用实体框架，我发布了 SQL 语句以便于理解。

从§5.2.6/1我们有（重点是我的）：

后缀 ++ 表达式的值是其操作数的值。[注意：获得的值是原始值的副本-结束注释]操作数应为可修改的左值。操作数的类型应为除 cv bool 以外的算术类型，或指向完整对象类型的指针。操作数对象的值通过加 1 来修改。++表达式的值计算在操作数对象修改之前排序. 对于不确定顺序的函数调用，后缀 ++ 的操作是单次求值。[ 注意：因此，函数调用不应干预左值到右值的转换以及与任何单个后缀 ++ 运算符相关的副作用。— 尾注] 结果是纯右值。结果的类型是操作数类型的 cv 非限定版本。如果操作数是不能表示递增值的位域，则位域的结果值是实现定义的。另见 [expr.add] 和 [expr.ass]。

也就是说，操作数对象的修改是在表达式的值计算之后排序++的。

从§5.18/1我们有（重点是我的）：

赋值运算符 (=) 和复合赋值运算符都从右到左分组。所有这些都需要一个可修改的左值作为它们的左操作数，并返回一个指向左操作数的左值。如果左操作数是位域，则所有情况下的结果都是位域。在所有情况下，赋值都在左右操作数的值计算之后和赋值表达式的值计算之前进行排序。对于不确定顺序的函数调用，复合赋值的操作是单次求值。[注意：因此，函数调用不应干预左值到右值的转换以及与任何单个复合赋值运算符相关的副作用。——尾注]

赋值表达式：
      条件表达式
      逻辑或表达式 赋值运算符 初始化子句
      抛出表达式

赋值运算符：
      = *= /= %= += -= >>= <<= &= ^= |=之一

在赋值运算符的左右操作数的值计算之后，赋值也是排序的。

因此，如果我们考虑表达式

我们从 §5.2.6/1 知道表达式的副作用i++，在这个赋值表达式的 RHS 上是在 的值计算之后排序的i++。并且从 §5.18/1 中我们知道，赋值运算符对 LHS 的赋值对应的副作用i是在赋值运算符的左右操作数的值计算之后排序的。

但是我如何证明这两个副作用是未排序的，以证明表达式i = i++;显示未定义的行为？

我想使用遗传算法解决作业车间调度问题，代码将用 Python 编写。

目前，我将个人作为[job, operation, machine, operation]. 例如，这是一条染色体的示例：

列表必须满足每个作业的操作优先级约束，例如列表中作业 1 的正确顺序是

换句话说，我必须仅在其他作业保留在其位置时才为作业 1（索引 0、索引 2 和索引 7）进行排序。正确的结果将是：

到目前为止我的尝试：

确定/过滤包含作业 1 的所有行：

输出

我正在尝试编写一个脚本，给定一组（小）常量的偏序，找到可以构建为给定偏序约束的扩展的总顺序（即线性扩展）。

例如，如果a,b,c,d作为常数和a>b && b>d约束给出，程序应该输出这些排序中的任何一个（或所有，如果可行的话 - 线性扩展是#P-complete）：

这是我第一次尝试使用 z3py：

这些是我的问题：

1. 为什么在定义为的常量上使用总体IntSort约束时会超时？
2. 有没有办法获得模型的更有用的表示（例如a<b<c<d）？（相关问题：链接）
3. 有没有更好的方法或更合适的工具来解决这个问题？

提前感谢您的帮助！

我想实现一个方法来比较我的接口的两个对象Task。由于只有严格的偏序，当且仅当两个对象不可比较时才应该返回。TaskpartialCompareTonull

如果您对严格偏序的概念感到困惑，请查看： https ://en.wikipedia.org/wiki/Partially_ordered_set

动机：有些任务会受到限制，即必须在另一项任务之前或之后完成。然后将其用于对任务进行拓扑排序，即以满足所有约束的方式排列它们。

Task a对于and的任何实例，它应该具有以下属性b：

• 如果a.partialCompareTo(b) != null那么sgn(a.partialCompareTo(b)) = -sgn(b.partialCompareTo(a))
• 如果a.partialCompareTo(b) = null那么b.partialCompareTo(a) = null

注意：我不能使用标准库的接口，因为Task:在returnComparable中没有总排序，所以如果两个对象是incomparable ，就没有足够的结果。特别是会有 Task 的实现，其中实现的实例永远不能相互比较（但可能与Task 的其他子类的实例相比较，这些实例覆盖）。compareToComparableint partialCompareTo

这个想法是使用partialCompareTo参数的方法，如果它覆盖了类中指定的方法Task。

下面的方法实际上更像是一个玩笑而不是实际的尝试，因为每次比较两个不可比较的对象时，我们都会得到一个 StackOverflowError （它被捕获，但无论如何这是不可行的）：

以下实现显然更好，但它有一个缺点，即总是必须覆盖辅助方法overridesDefaultPartialCompareTo：

有没有办法问，方法是否在代码中被覆盖？

还是有其他方法可以解决我的问题？

输入：元素数组和这些元素子集的偏序，被视为约束集。

输出：满足偏序的数组（或任何有序序列）。

问题：如何有效地实现重新排序？与原始输入序列相比，引入的反转（或交换）的数量应尽可能小。请注意，可以为任意数量的元素定义偏序（某些元素可能不是其中的一部分）。

上下文：它源于 2 层图交叉减少的情况：在交叉减少阶段之后，我想重新排序一些节点（因此，部分顺序可能只包含一个小子集）。

总的来说，我的想法是稍微弱化这一点，并仅针对属于偏序的元素解决问题（尽管我认为这可能会导致非最佳结果）。因此，如果我有一个序列 ABCDE 并且偏序只包含 A、B 和 E，那么 C 和 D 将保持在同一个位置。它以某种方式让我想起了 Kemeny 分数，但我还不能把它变成算法。

可以肯定的是：我不是在寻找拓扑排序。这可能会引入比所需更多的反转。

编辑1：

• 更改了措辞（序列到数组）。
• 用于解决问题的额外空间量可以是任意的（嗯，多项式有界）。当然，越少越好 :) 所以，像 O(ArrayLen*ArrayLen) 这样的东西最多会很棒。
• 为什么交换或反转的最小数量：由于此过程是交叉减少的一部分，因此输入数组的排序（希望）接近最佳值，就与第二节点层的边缘交叉而言。然后，每一次额外的交换或反转可能会再次引入边缘交叉。但是在计算输出的过程中，完成的交换或移动的数量并不重要（尽管再次，线性或二次的东西会很酷），因为只有输出质量很重要。现在，我要求约束是一个总顺序，并且只检查该顺序的节点，因此解决它变得微不足道。但是偏序约束会更加灵活。

我正在尝试创建一种通过以下方式对列表进行排序的方法：

但我在Comprator javadoc中读到，比较需要是一个总排序关系。也就是说，除非它们相等，否则没有两个比较器可以具有相同的优先级。情况可能并非如此。

我正在尝试这个简单的比较器：

当然，我可以使处理器具有可比性，但我想避免对所有处理器进行修改。有没有办法用流对它们进行排序？作为替代方案，我可以编写自己的方法或创建更复杂的比较器，但我对缺乏更优雅的解决方案感到惊讶。

以下代码不进行类型检查：

Isabelle 在引理处抱怨以下错误：

为什么这样？我错过了使用解释的东西吗？我怀疑我在这里需要一个新类型包装器之类的东西......

我可以得到的所有编译器都同意这很好：

但是，根据 gcc，以下代码（带有无法从函数参数推导出的前导模板参数）是模棱两可的：

另一方面，clang、msvc 和 icc 对此非常满意。

哪个编译器是对的？

优先参考标准的相应部分。

在 Scala 中对集合进行部分排序询问如何在 Scala 中按 PartialOrdering 进行排序。评论指出作者不应该在给出的示例中进行部分排序。我确实需要按偏序排序——我有可能是其他国家飞地的国家，这会导致偏序。

那么：给定 a List[T], where Textends PartialOrdering[T], 是否有一种根据偏序排序的合理方式？