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

• Z时代
• 2024-01-10
• 分类：问答

在不加载其他库的情况下，如何在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

以上是 基数R中的排列之间的Kendall tau距离（又称气泡排序距离） 的全部内容， 来源链接： utcz.com/qa/420805.html