Trier la liste des éléments par relations

Question

Dans une application que je suis en train de réaliser, on me donne une liste d'éléments, et des relations entre eux, et je dois calculer une liste triée. Pour le plaisir, utilisons un exemple de notation d'examen, nous savons que :

1. John a fait mieux que Jane

2. Jane a fait pire que Luke

3. Luke a fait mieux que Jason

4. Jason a fait pire que Tim

Pour cette liste, je dois calculer la liste triée suivante :

1. John
2. Luke
3. Jane
4. Tim
5. Jason

Comment déduire la position d'un élément dans la liste triée, sur la base des relations contestées ?

Answer 1

Fondamentalement, Le triage nécessite un ordre linéaire .

Vous avez besoin que votre relation soit un ordre linéaire, ce qui signifie :

1. a ≤ a (réflexivité)
2. si a ≤ b et b ≤ a alors a = b (antisymétrie)
3. si a ≤ b et b ≤ c alors a ≤ c (transitivité)
4. pour tout a et b, a ≤ b ou b ≤ a (totalité)

Alors, qu'est-ce que ça veut dire ? La plupart des relations habituelles sont linéaires. Par exemple, si vous parlez de notes, qui sont en fait des nombres réels, alors oui, les notes peuvent être ordonnées linéairement. Les classements aussi, puisqu'ils ne sont eux aussi que des nombres réels.

Mais par exemple, si vous classez des joueurs d'échecs, vous ne pouvez pas utiliser l'historique de leurs matchs. Si le joueur A a battu le joueur B dans la majorité de ses matchs, et que B a de nouveau battu C dans la majorité de ses matchs, cela ne signifie PAS que A > B > C, simplement parce que C peut avoir battu A dans la majorité de ses matchs.

C'est d'ailleurs l'une des raisons pour lesquelles Classement Elo existe, ils avaient besoin d'un ordre linéaire pour trier qui est le meilleur joueur, et remarquez comment Elo est essentiellement un nombre réel, donc a un ordre linéaire.

Donc, pour la notation des examens, vous n'avez tout simplement PAS cet ordre linéaire. Pourquoi ? Il s'agit de nombres réels ! Eh bien, c'est vrai, vous avez cet ordre linéaire, mais vous ne pouvez pas tout demander à cet ordre linéaire, vous êtes limité à la liste de comparaison prédéfinie, qui est ici :

1. John a fait mieux que Jane
2. Jane a fait pire que Luke
3. Luke a fait mieux que Jason
4. Jason a fait pire que Tim

Donc, la réponse est : Non, en général, vous ne pouvez pas trier une liste si vous ne disposez pas de la comparaison entre une paire d'éléments.

Maintenant, je travaille sur une réponse "moins mauvaise", mais ce n'est pas trivial pour moi...

---

Edit : OK, j'ai trouvé quelque chose. L'idée est que vous allez extraire le plus d'informations possibles sur votre liste de comparaison prédéfinie. Puis traiter toute comparaison qui n'est pas dans votre liste de comparaison étendue comme une égalité.

Alors, comment faites-vous ?

Tout d'abord, pour toute comparaison a < b, vous ajouterez l'entrée b > a. Ensuite, vous chercherez dans votre liste de comparaisons prédéfinies toute comparaison a < b et b < c et ajouterez (si elle n'y figure pas déjà) toute comparaison correspondante a < c (transitivité) et c > a. Si vous savez qu'il n'y a pas d'égalités (aucun élève n'a la même note), c'est terminé. Sinon, il faut ajouter toutes les relations de réflexivité et d'antisymétrie. Vous ne pouvez rien faire pour la totalité. Maintenant, vous avez votre liste de comparaison étendue.

Maintenant, prenez votre algorithme de tri préféré. Si vous n'en avez pas, quicksort est agréable, efficace et court à écrire. Ensuite, chaque fois que l'algorithme demande une comparaison entre a et b, regardez plutôt votre liste de comparaison étendue. Si la comparaison se trouve ici, tant mieux, sinon, traitez la comparaison comme a=b. (Notez que le fait que vous sachiez qu'il n'y a pas d'égalités n'a aucune importance, l'algorithme s'en moque).

Le résultat sera une liste triée "le moins mal". Il existe généralement plusieurs listes triées "le moins mal" possibles, mais cet algorithme ne vous en donnera qu'une seule.

---

Alors, donnons un exemple. C'est presque le même que celui donné dans le PO, avec une légère différence ("Jean a fait pire que Luc" au lieu de "Jeanne a fait pire que Luc"). donc, nous commençons par :

1. John a fait mieux que Jane
2. John a fait pire que Luke
3. Luke a fait mieux que Jason
4. Jason a fait pire que Tim

Maintenant, pour chaque "X est pire que Y", j'ajoute "Y est meilleur que X", et vice-versa. Les nouvelles phrases sont en gras :

1. John a fait mieux que Jane
2. Luke a fait mieux que John
3. Luke a fait mieux que Jason
4. Tim a fait mieux que Jason
5. Jane a fait pire que John
6. John a fait pire que Luke
7. Jason a fait pire que Luke
8. Jason a fait pire que Tim

Enfin, je scanne toutes les phrases possibles "X a fait mieux que Y" et "Y a fait mieux que Z", et j'ajoute "X a fait mieux que Z".

1. John a fait mieux que Jane
2. Luke a fait mieux que John
3. Luke a fait mieux que Jason
4. Tim a fait mieux que Jason
5. Luke a fait mieux que Jane
6. Jane a fait pire que John
7. John a fait pire que Luke
8. Jason a fait pire que Luke
9. Jason a fait pire que Tim
10. Jane a fait pire que Luke

La table étendue est terminée.

Voyons maintenant le pseudo-code de quicksort :

  function quicksort('array')
      if length('array') ≤ 1
          return 'array'  // an array of zero or one elements is already sorted
      select and remove a pivot value 'pivot' from 'array'
      create empty lists 'less' and 'greater'
      for each 'x' in 'array'
          if 'x' ≤ 'pivot' then append 'x' to 'less'
          else append 'x' to 'greater'
      return concatenate(quicksort('less'), 'pivot', quicksort('greater'))

Le site seulement La différence avec le quicksort standard est que vous ne pouvez généralement pas connaître la réponse à la question if('x' ≤ 'pivot') ... . Donc, à la place, si x=Luke y pivot = Tim vous cherchez dans votre tableau la phrase "Luc a fait pire que Tim". Si vous la trouvez, alors vous considérez que la réponse est true et faire append 'x' to 'less' . Si vous trouvez dans le tableau "Luc a fait mieux que Tim", alors vous considérez que la réponse est fausse, et vous faites append 'x' to 'greater' . Et enfin, si vous ne trouvez aucune des deux phrases mentionnées ci-dessus, vous faites comme si 'x' == 'pivot' et vous le faites. append 'x' to 'less'

Answer 2

Si vous lancez un http://en.wikipedia.org/wiki/Topological_sorting algorithme, vous pouvez examiner le résultat pour voir si deux personnes sont dans un ordre fixe : si c'est le cas, l'une sera joignable par l'autre. Si vos données sont cohérentes, un tri topologique vous donnera un ordre linéaire qui est cohérent avec vos données, mais peut impliquer des ordres que vos données ne soutiennent pas réellement, en raison du manque de comparaisons pour dire si Adam a vraiment fait mieux que Bill.

À moins que vos données ne soient très spéciales, vous trouverez probablement quelques cas où il y a des cycles dans le graphique et où aucun ordre n'est cohérent. Vous pouvez trouver des groupes de personnes liés dans de tels cycles avec http://en.wikipedia.org/wiki/Strongly_connected_component .

Si vous devez résoudre des données bruyantes et incohérentes, vous devrez probablement vous tourner vers une sorte de système de classement statistique. Il existe une sorte de résumé à http://en.wikipedia.org/wiki/Pairwise_comparison . Une recherche plus poussée sur Internet vous montrera que le modèle Bradley-Terry peut être ajusté de diverses manières, y compris par régression logistique, et qu'il s'agit donc d'un point de départ, bien qu'il existe bien sûr une grande variété d'autres systèmes de notation, dont certains sont associés à des sports et des jeux tels que http://en.wikipedia.org/wiki/Elo_rating_system