从排序想起

考虑,从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的.
每一条边的移除都可能影响每一对节点的最短路径开销.

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

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