我正在做一些补偿.数学工作,我正在尝试使用复杂的数学排序谓词对序列进行排序,该序列并不总是在序列中的两个元素之间定义.我正在尝试更多地了解排序算法,这些算法可以优雅地处理无法进行的元素比较,因为到目前为止我只管理了一个非常基本的方法.
我很抱歉,如果这个问题是一些经典问题,我需要一些时间来定义它,算法设计不是我的强项.
假设我有一个序列A = {a, b, c, d, e}.让我们定义f(x,y)为一个二元函数,通过应用一些复杂的排序标准来返回0if x < y和1if y <= x.
在正常情况下,这将为我们提供足够的细节进行排序A.但是,如果排序标准没有为该特定输入对定义良好,f也可以返回-1.一对输入的未定义是可交换的,即 f(q,r)当且仅当未定义时,它f(r,q)是未定义的.
我想尝试A使用明确定义的排序标准对序列进行排序.
例如,让我们假设
f(a,d) = f(d,a) 未定义. f 都是明确定义的.然后,尽管不知道a和之间的不等式关系d,我们将能够A基于明确定义的排序标准进行排序,只要 在得到的"排序"序列中彼此相邻a并且d彼此不相邻.
例如,假设我们首先确定的相对排序A - {d}是{c, a, b, e},因为所有这些对向f是明确定义的.这可以调用任何排序算法.
然后我们可以打电话f(d,c),和
d < c我们完成了 - 排序的顺序确实如此{d, c, a, b, e}.f(a, d).这是未定义的,所以我们无法d从这个角度确定位置.f(d, e),并从元素方向向右移动.
x在那里d > x,我们正在这样做.f(a, d)再次进行比较,我们已经确定我们无法根据我们定义的明确排序标准对序列进行排序.这些排序算法是否有分类,它们处理未定义的比较对？
更好但是没有预料到,有一种众所周知的"有效"方法吗？我已经定义了我自己极其简陋的蛮力算法来解决这个问题,但我确信它并不理想.
它有效地抛出了遇到时无法比较的所有序列元素,并且在穷举地尝试将所有与所有其他元素不可比较的序列元素放入已排序的子序列之前,如果剩余任何元素则对剩余的子序列进行排序.
只需要进一步研究这个主题的路径就会很棒 - 我缺乏算法经验,因此很难找到我应该在哪些方面寻找关于这些问题的更多背景知识.
这与拓扑排序非常接近,您的二元关系是边缘.特别是,这只是将部分订单扩展为总订单.如果你考虑使用toposort的所有对(即O(V + E)),你会有最坏情况的O(n ^ 2)算法(实际上是O(n + p),其中n是元素的数量,p是数量可比对).