R implémentation du tri par inversions

Question

Je me demandais s'il existait une implémentation dans R où trie une permutation de n nombres dans la séquence 1 ... n originale et fournit le nombre d'inversions nécessaires. Par exemple, une implémentation du "tri par inversion" ou du "tri par translocation" comme indiqué dans ce ppt.

Plus précisément, j'ai une permutation d'une séquence de n éléments, pi (n), et je veux comprendre à quel point il est proche de la séquence originale. Le nombre d'inversions semble être une bonne mesure.

Merci!

Answer 1

Cela ressemble à un travail pour la distance de Kendall (aussi connu, parfois, que la distance de tri Bubble). C'est probablement la métrique la plus couramment utilisée pour mesurer la distance dans l'espace de classement.

La distance de Kendall compte le nombre de fois que deux séquences diffèrent dans l'ordre des éléments dans deux indices. Dans le cas où l'une des séquences est la séquence triviale (1, 2, ..., n), on peut mesurer la distance simplement en comptant le nombre de fois que i < j et pi (i)> pi (j) .

Si vous aimez cette métrique (elle équivaut au nombre minimum de transpositions par paire d'éléments adjacents que vous auriez à compléter pour transformer une séquence en 1: n), vous pouvez la trouver dans mon package, RMallow, disponible sur CRAN. La fonction s'appelle AllSeqDists. Voici un exemple:

library(RMallow) 
# Create a matrix of sequences, each of length 5 
datas <- matrix(c(1:5, 5:1, c(2, 1, 3, 4, 5), c(5, 1, 2, 3, 4), c(1, 2, 4, 5, 6), c(1, 5, 6, 2, 4)), nrow = 6, byrow = TRUE) 
# Calculate all of their Kendall distances to the sequence (1, 2, 3, 4, 5) 
datas <- SimplifySequences(datas) 
dists <- AllSeqDists(datas) 

Vous pourriez également considérer la métrique de Spearman.
En outre, il existe une classe de modèles sur les données de classement que je dois brancher appelée "modèles Mallows", en fonction de ce que vous voulez faire.