基数R中的排列之间的Kendall tau距离(也称为气泡排序距离)

问题描述

在不加载其他库的情况下，如何在R中计算两个排列之间的Kendall tau距离(也称为气泡排序距离)?

How can the Kendall tau distance (a.k.a. bubble-sort distance) between two permutations be calculated in R without loading additional libraries?

推荐答案

在阅读后，这里是一个O(n.log(n))实现，但是我怀疑可能会有更好的R解决方案.

Here is an O(n.log(n)) implementation scraped together after reading around, but I suspect there may be better R solutions.

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)]))
}

如果需要自定义平局，则必须在标记为# ***

If one needs custom tie-breaking one would have to fiddle with the last condition on the line marked # ***

用法:

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

这篇关于基数R中的排列之间的Kendall tau距离(也称为气泡排序距离)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！