Расстояние Кендалла Тау (расстояние пузырьковой сортировки) между перестановками в базе R

Question

Как рассчитать расстояние Тау Кендалла (расстояние пузырьковой сортировки) между двумя перестановками в R без загрузки дополнительных библиотек?

Answer 1

Вот реализация 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

Answer 2

Хммм. Кто-то заинтересован в том же, над чем я работал.

Ниже мой код на Python.

from collections import OrderedDict


def invert(u):
    identity = sorted(u)
    ui = []
    for x in identity:
        index = u.index(x)
        ui.append(identity[index])
    print "Given U is:\n",u
    print "Inverse of U is:\n",ui
    return identity,ui

def r_vector(x,y,id):
    # from collections import OrderedDict
    id_x_Map = OrderedDict(zip(id,x))
    id_y_Map = OrderedDict(zip(id,y))
    r = []
    for x_index,x_value in id_x_Map.items():
        for y_index,y_value in id_y_Map.items():
            if (x_value == y_index):
                r.append(y_value)

    print r
    return r

def xr_vector(x):
    # from collections import OrderedDict
    values_checked = []
    unorderd_xr = []
    ordered_xr = []

    for value in x:
        values_to_right = []
        for n in x[x.index(value)+1:]:
                    values_to_right.append(n)
            result = [i for i in values_to_right if i < value]
            if(len(result)!=0):
                values_checked.append(value)
                unorderd_xr.append(len(result))

    value_ltValuePair = OrderedDict(zip(values_checked,unorderd_xr))

    for key in sorted(value_ltValuePair):
        # print key,value_ltValuePair[key]
        ordered_xr.append(value_ltValuePair[key])
    print "Xr= ",ordered_xr
    print "Kendal Tau distance = ",sum(ordered_xr)



if __name__ == '__main__':
    print "***********************************************************"
    print "Enter the first string (U):"
    u = raw_input().split() 
    print "Enter the second string (V):"
    v = raw_input().split()
    print "***********************************************************"

    print "Step 1: Find U Inverse"
    identity,uinverse = invert(u)
    print "***********************************************************"

    print "Step 2: Find R = V.UInverse"
    r = r_vector(v,uinverse,identity)
    print "***********************************************************"

    print "Step 3: Finding XR and Kenday_Tau"
    xr_vector(r)

Что касается подхода / алгоритма, позволяющего найти расстояние Кендалла Тау таким образом, я бы либо оставил его вам, либо указал на исследовательскую статью " Оптимальные коды перестановки" и τ-метрику Кендалла.

Вы можете реализовать (подход) то же самое в R.

Answer 3

Вы могли бы использовать

(choose(length(x),2) - cov(x,y,method='kendall')/2)/2

если вы знаете, что оба из входных списков x а также y не содержат дубликатов.