美文网首页
从排序想起

从排序想起

作者: zizon | 来源:发表于2019-07-29 00:07 被阅读0次

考虑,从set S中根据偏好P选取一个元素E.
本质上就是用P对S进行排序的问题.

或者说order的问题.

考虑通常意义上的三个关系.
大于,等于,小于.

考虑没有symmetry/cyclic的情况.
即,大于小于的一个order chain不构成一个环.

那么大于小于可以合并为一个符号.

定义等于为=,非对称的大于小于为!=.

则给定任意a,b.
两者要么是=,要么是!=.

换一套符号表示的话.
f({a,b})= {=,!=} = {0,1}就算某种形式的binary classification.

考虑到前面的非对称限定,f({a,b})可能undefined的话.
回归三值,=,>和<,就是triple/muti classification.

那么从这个角度看.
排序的数组就是某种形式的index结构.
索引的是所有可能组合的分类结果情况.

也就是从element e->number index -> {=,>,<}的一个路径.

formalize的话.
就是给定一个set X,如果存在一个映射f.
满足f(x \in X) = N.
使得C(f(a),f(b)) = {=,!=} = {0,1}

如果是一个multi class的话,给定number of class=K
C(f(a),f(b)) = C_k(f(a),f(b)) = 1; C_{k-1}(f(a),f(b)) = 0.
也就是将为零的递归下去.

但是这个f不一定存在.
因为可能根本不是有序定义的.

但如果存在的话,如何去寻找这一个f呢?

如果ab所在的set S是有限的话.
那么实际上C是一个确定的集合.

此时的f只要任意一组满足C的数列就行了.
而这样的数列可以在排序过程中构建.

如果S是不确定的呢?

这样的S可以分开为一个确定的集合S_0和一个非确定的集合S_u.
确定的部分如上构建.

S_u的元素可以是S_0中相邻gap之间的任意一个数.
因为未知的S_u的元素必然是在S_0的L(S_0)+1的区间内.

于是未知元素的问题就是对于这几个区间归属的概率问题.

实际上,如果这个f确实存在,且是严格有序的.
那么新元素的问题实际上是一个插入问题.

所以f_u实际上是一个关于f的插入生成.

如果f不存在呢?

考虑S都是可比较的情况.

f不存在以图视角看待的话,S的路径存在回环.

因为如果不存在的回环的话,意味着元素都存在单向路径.
也就是存在严格的有序状态.

那么一个近似的解自然就是切断回环路径.

这样的话,主要就是图的partition问题了.

但这可能没有一个很好的方式去估算?
因为实际上这个图是fully connected的.
每一条边的移除都可能影响每一对节点的最短路径开销.

所以可能更实际的方式是做子图划分.
以期望得到的子图是符合预期的.

尽管同样地,似乎这种划分也不见得就有一个很好的代价衡量方式.

相关文章

  • 从排序想起

    考虑,从set S中根据偏好P选取一个元素E.本质上就是用P对S进行排序的问题. 或者说order的问题. 考虑通...

  • 数据结构-排序(OC实现)

    从大类分,排序分为外排序和内排序。内外排序的区别在于是否需要多次从内存外读取数据进行排序。外排序是要多次从外存读取...

  • 震惊!!JAVA中选择排序竟然是这样子的!

    说到选择排序,可能会想起冒泡排序。 冒泡排序和选择排序不禁会问它们有什么区别? 的确, 它们的基本思想是一样...

  • 不同的表达方式20211031

    今天回顾各种排序算法,我注意到对于每种排序算法,看到名字并不能想起这个排序算法是如何完成排序的。 我过去尝试过使用...

  • 排序方法

    选择排序:每次从【未排序】中选取最小的元素放置到【已排序】的末尾插入排序:每次从【未排序】中选取第一个元素放置到【...

  • iOS重做轮子,写一个NSDictionary(一)

    从排序说起 一种很棒的排序算法,木桶排序(计数排序)。 算法如下,比如[ 1 9 3 7]需要排序。按木桶排序,...

  • 排序算法

    冒泡 选择排序 从队列中挨个选出最小的,放在最前面 插入排序 希尔排序 归并排序 快速排序 堆排序 计数排序 桶排...

  • 20 ,Arrays.sort排序

    从小到大排序 从大到小排序

  • 基础排序算法总结(七种排序算法C代码)

    排序是最基础的算法,从排序的对象来说主要分为内部排序和外部排序。内部排序主要是针对内存中的数据进行排序,外部排序针...

  • 冒泡排序(Bubble Sort)以及改进

    冒泡排序(Bubble Sort) 最简单写法 冒泡排序改进 优化:从尾部开始向前移动 好处在于:排序时候从后边开...

网友评论

      本文标题:从排序想起

      本文链接:https://www.haomeiwen.com/subject/gmbmrctx.html