A transitividade é necessária para um algoritmo de classificação

É possível usar um algoritmo de classificação com uma comparação não transitiva e, se sim, por que a transitividade é listada como um requisito para classificar comparadores?

Fundo:

• Um algoritmo de classificação geralmente classifica os elementos de uma lista de acordo com uma função comparadora C (x, y), com

  $$\begin{array}{ll} C(x,y) = \begin{cases} -1 & {\text{if}}\ x\prec y \\ 0 & {\text{if}}\ x\sim y \\ +1 & {\text{if}}\ x\succ y \\ \end{cases} \end{array}$$

  Os requisitos para esse comparador são, tanto quanto eu os entendo:

  • reflexivo: $\forall x: C(x,x)=0$
  • antissimétrico: $\forall x,y: C(x,y) = - C(y,x)$
  • transitivo: $\forall x,y,z, a: C(x,y)=a \land C(y,z)=a \Rightarrow C(x,z)=a$
  • C (x, y) é definido para todos os x e y, e os resultados dependem apenas de x e y

  (Esses requisitos sempre são listados de maneira diferente em diferentes implementações, portanto, não tenho certeza de que os atendi corretamente)

Agora estou pensando em uma função comparadora "tolerante", que aceita os números x, y como semelhantes se : C ( x , y ) = { - 1 se x < y - 1 0 se | x - y | ≤ 1 + 1 se x > y + $|x - y| \le 1$

Exemplos: ambos [ 1, 2, 3, 4, 5]e [1, 4, 3, 2, 5]são classificados corretamente em ordem crescente, de acordo com o comparador tolerante ( se x vier antes de y na lista), mas não é, pois C (4,2) = 1$C(x,y) \le 0$
[1, 4, 2, 3, 5]

Este comparador tolerante é reflexivo e anti-simétrico, mas não transitivo.

ie C (1,2) = 0, c (2,3) = 0, mas C (1,3) = -1, violando a transitividade

No entanto, não consigo pensar em nenhum algoritmo de classificação que falhe em produzir uma saída "classificada corretamente" quando recebida esse comparador e uma lista aleatória.

Portanto, a transitividade não é necessária neste caso? E há uma versão menos rígida do transitividade que é necessário para a classificação para o trabalho?

Perguntas relacionadas:

• Por que a antisimetria é necessária para a classificação comparada? (sobre antisimetria)
• Algoritmos de classificação que aceitam um comparador aleatório (aproximadamente um C aleatório (x, y))
• OrderBy com um IComparer não transitivo (sobre o algoritmo de classificação c #, por mim)

Você perguntou: Podemos executar um algoritmo de classificação, alimentando-o como um comparador não-transitivo?

A resposta: claro. Você pode executar qualquer algoritmo com qualquer entrada.

No entanto, você conhece a regra: Garbage In, Garbage Out. Se você executar um algoritmo de classificação com um comparador não-transitivo, poderá obter uma saída sem sentido. Em particular, não há garantia de que a saída será "classificada" de acordo com o seu comparador. Portanto, executar um algoritmo de classificação com um comparador não-transitivo provavelmente não será útil da maneira que você provavelmente esperava.

$[3, 2, 1]$

Dado um conjunto de elementos e uma relação de ordenação binária, a transitividade é necessária para ordenar totalmente os elementos. De fato, a transitividade é necessária para definir uma ordem parcial dos elementos. http://en.m.wikipedia.org/wiki/Total_order

Você precisaria de uma definição muito mais ampla do que "classificado" significa para classificar elementos sem transitividade. É difícil ser auto-consistente. Outra resposta diz "Em particular, não há garantia de que a saída será 'classificada' de acordo com o seu comparador". Mas podemos dizer algo muito mais forte. Você tem certeza de que a saída não será classificada de acordo com o seu comparador.

$a<b$$b<c$$c<a$

Parece que o que você deseja é organizar itens de forma que todas as classificações discerníveis estejam corretas, mas itens próximos podem ser considerados "indistinguíveis". É possível projetar algoritmos de classificação que funcionem com essas comparações, mas, a menos que haja limites para quantas comparações reportarem que as coisas são indistinguíveis, não há como evitar que elas exijam comparações N (N-1) / 2. Para entender o porquê, escolha um número N e qualquer algoritmo de classificação que faça menos que N (N-1) / 2 comparações. Em seguida, preencha uma lista L [0..N-1], definindo cada elemento L [I] como I / N e "classifique" usando seu comparador (o valor mínimo será 0 e o máximo (N-1) / N , então a diferença será (N-1) / N, que é menor que 1).

Como existem N (N-1) / 2 pares de itens que poderiam ser comparados e o tipo não fez tantas comparações, deve haver alguns pares de itens que não foram diretamente comparados entre si. Substitua o que acabou sendo classificado primeiro por 1 e o outro por -1 / N, reverta todos os itens para sua posição inicial e repita a operação de classificação. Cada operação de comparação simples produzirá zero, assim como ocorreu na primeira vez; portanto, as mesmas comparações serão realizadas e os itens terminarão na mesma sequência. Para que a lista seja classificada corretamente, o "1" teria que classificar após o "-1 / N" (já que diferem em mais de um), mas como o algoritmo de classificação nunca compararia esses dois itens diretamente entre si, não teria como saber disso.

Preencha uma matriz de n elementos com os valores n, n-1, n-2, ..., 2, 1. Em seguida, tente classificar usando o algoritmo de "inserção direta". Você descobrirá que cada elemento é considerado igual ao elemento logo antes e, portanto, não é movido. O resultado da "classificação" é a mesma matriz.