Como classificar objetos baseados apenas em relacionamentos "menos que" "

Question

Diga que eu tenho n objetos, cada um com um valor desconhecido, e um por n matriz z. tal que z (i, j)= 1 se o valor do objeto eu for menor que o valor do objeto J e Z (i, j)= 0 Caso contrário.Como posso classificar esses n objetos, dada apenas a matriz z?

Answer 1

O que você está procurando é um Classe de comparação . Por favor, dê uma olhada nesse artigo.

---

Deixe-nos declarar claramente o requisito para quaisquer dois objetos, objeto I e Objeto J quando eles aparecerem na lista definida final. Objeto que eu devo ocorrer antes do objeto J se Z (I, J)= 1. Objeto, posso ocorrer antes ou depois do objeto J se Z (I, J)= Z (j, i)= 0.

Como Vonbrand mencionado, devemos supor que a matriz z especifica uma relação "menos de" definida "ou, em termos de matemática, uma ordem rigorosa sobre os valores dos objetos. Caso contrário, os objetos dados podem não ser classificados.

• z [i, j]= 0 se z [j, i]= 1. Caso contrário, não podemos classificar objeto I e objeto j.
• z [j, i]= 0 se z [i, k]= 1 e z [k, j]= 1 para alguns k. Caso contrário, não podemos classificar objeto I, J e K (pense em papel-tesoura-rock).

---

Suponha que Z especifique uma relação "menor que" definida. Em seguida, ele também define um " $ \ le $ " operação de comparação naturalmente. Ou seja, se Z (j, i)= 0, então objeto I $ \ le $ objeto j. Para que possamos aplicar qualquer tipo de comparação para classificar o objeto $ n $ objeto.

Quase todos os algoritmos de classificação são tipos de comparação. Por exemplo, QuickSort, MergeSort, tipo de inserção, tipo de seleção e tipo de bolha. Uma exceção notável é contagem de classificar .