基数R中的排列之间的Kendall tau距离（又称气泡排序距离）

基数R中的排列之间的Kendall tau距离（又称气泡排序距离）

这是一个O（n.log（n））实现，在阅读后一并刮过，但是我怀疑可能会有更好的R解决方案。

inversionNumber <- function(x){    mergeSort <- function(x){        if(length(x) == 1){ inv <- 0 #printind(' base case')        } else { n <- length(x) n1 <- ceiling(n/2) n2 <- n-n1 y1 <- mergeSort(x[1:n1]) y2 <- mergeSort(x[n1+1:n2]) inv <- y1$inversions + y2$inversions x1 <- y1$sortedVector x2 <- y2$sortedVector i1 <- 1 i2 <- 1 while(i1+i2 <= n1+n2+1){     if(i2 > n2 || (i1 <= n1 && x1[i1] <= x2[i2])){ # ***         x[i1+i2-1] <- x1[i1]         i1 <- i1 + 1     } else {         inv <- inv + n1 + 1 - i1         x[i1+i2-1] <- x2[i2]         i2 <- i2 + 1     } }        }        return (list(inversions=inv,sortedVector=x))    }    r <- mergeSort(x)    return (r$inversions)}

。

kendallTauDistance <- function(x,y){    return(inversionNumber(order(x)[rank(y)]))}

如果需要定制抢七，则必须在标记的行上摆弄最后的条件

# ***

用法：

> kendallTauDistance(c(1,2,4,3),c(2,3,1,4))[1] 3