# What's the Kendall Tau's distance between these 2 rankings?

ranking i: {3, 1, 2}

ranking j: {2, 1, 3}

I am referring to the Wikipedia page here, and to calculate the Kendall distance, I just need to count the number of times the values in ranking i are in the opposite order of the values in ranking j.

3 < 1 in ranking i, but 3 > 1 in ranking j

3 < 2 in ranking i, but 3 > 2 in ranking j

1 < 2 in ranking i, but 1 > 2 in ranking j

There are 3 switches, so the Kendall distance is 3. However when I call a function to calculate the Kendall's distance in R, it returns 1. What's the correct Kendall's distance between these 2 rankings?

• The wiki says the distance is the total number of discordant pairs of observations (that is, it is Q in the formula of Gamma or Kendall's tau). Consider the pairs of observations (columns): i(3>1) and j(2>1) = concordant; i(1<2) and j(1<3) = concordant; i(3>2) but j(2<3) = discordant. One discordant pair. Commented Aug 24, 2015 at 20:47
• If it's [3,1,2] vs [2,1,3] the number of discordant pairs here is 3 out of 3. If you use Python's scipy Kendall’s tau function to calculate the correlation coefficient you'll get -1. The coefficient is defined as the ratio of concordant pairs minus the discordant pairs, in this case it's 0/3 - 3/3 Unless you're looking at it as indices and values, (let's say indices are letters) than: ranking i: a-3, b-1, c-2 = b-1, c-2, a-3 ranking j: a-2, b-1, c-3 = b-1, a-2, c-3 In that case the distance is 1. So perhaps the function in R looks at it this way
– Oleg
Commented Apr 8, 2020 at 3:55

The Kendall tau distance in your case is, indeed, 1.

See the following python code:

import itertools

def kendallTau(A, B):
pairs = itertools.combinations(range(0, len(A)), 2)

distance = 0

for x, y in pairs:
a = A[x] - A[y]
b = B[x] - B[y]

# if discordant (different signs)
if (a * b < 0):
distance += 1

return distance

ranking_i = [3, 1, 2]
ranking_j = [2, 1, 3]
assert kendallTau(ranking_i, ranking_j) == 1

• that wrong, the distance is 3. See other answers Commented Mar 31, 2020 at 9:20
• The function works ok, there's just confusion between orderings and ranks. The ordered list of objects 3 > 1 > 2 posed in the original question translates to assigned ranks of [2, 3, 1] (i.e. object 3 is ranked first, object 1 second, and object 2 third). Likewise, the list 2 > 1 > 3 takes assigned ranks of [2, 1, 3]. This answer assumes the ordered lists ('rankings') provided are themselves ranks assigned to objects (e.g. assuming in 'ranking i' that object 1 is ranked third, object 2 first, etc). Setting ranking_i = [2, 3, 1] and ranking_j = [2, 1, 3] yields the correct distance (3). Commented Sep 10, 2020 at 9:53

From Wikipedia: Kendall tau distance is also called bubble-sort distance since it is equivalent to the number of swaps that the bubble sort algorithm would take to place one list in the same order as the other list.

import itertools

def kendall_tau_distance(order_a, order_b):
pairs = itertools.combinations(range(1, len(order_a)+1), 2)
distance = 0
for x, y in pairs:
a = order_a.index(x) - order_a.index(y)
b = order_b.index(x) - order_b.index(y)
if a * b < 0:
distance += 1
return distance

print kendall_tau_distance([3,1,2], [2,1,3])
3

• I think you need to look again at the comment under the original question for the definition of Kendall distance. Commented Jan 25, 2018 at 14:37
• I think that the definition of Kendall tau distance in the comment under the original question is wrong. its not whats is in en.wikipedia.org/wiki/Kendall_tau_distance The Kendall tau rank distance between two rank orders is the total number of rank disagreements over all unordered pairs. Commented Jan 25, 2018 at 16:20
• @Cohensius It clearly says in the mathematical definition of $K(\tau_1 \tau_2)$ that you have to index the lists, also, in OP's question, you only need one single swap to make one list the same as the other (you swap indexes 1 and 3).
– Ash
Commented May 4, 2018 at 19:47
• ...counts the number of pairwise disagreements between two ranking lists: in the OP example: in ranking i: 3<1 while in ranking j: 1<3 in ranking i: 1<2 while in ranking j: 2<1 in ranking i: 3<2 while in ranking j: 2<3 Thats 3 pairwise disagreements Commented May 6, 2018 at 16:24
• @Ash the swaps need to be between adjacent items, so 3 is correct Commented Jul 17, 2019 at 14:31

The Kendall tau distance in this instance is 3. It is also known as Kemeny distance. See here and here.

In some fields rankings are also allowed to have ties, therefore the Kemeny could be considered as a distance of 6 instead of 3. That's a confusion that arises quite often. But in your situation it is 3 because ties are not allowed.

Kendell tau distance is the number of swaps which needs to be done for making the two lists the same. It can also be considered as a variant of Insertion Sort, where each swap adds +1 to Kendell distance.

• You don't answer the OP question. What's the correct Kendall's distance between these 2 rankings? Commented Mar 31, 2020 at 9:22