Kendall tau distance

The Kendall tau rank distance is a metric that counts the number of pairwise disagreements between two ranking lists. The larger the distance, the more dissimilar the two lists are. 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. The Kendall tau distance was created by Maurice Kendall.
Definition.
The Kendall tau ranking distance between two lists formula_1 and formula_2 is
where 
formula_9 will be equal to 0 if the two lists are identical and formula_10 (where formula_11 is the list size) if one list is the reverse of the other. Often Kendall tau distance is normalized by dividing by formula_10 so a value of 1 indicates maximum disagreement. The normalized Kendall tau distance therefore lies in the interval [0,1].
Kendall tau distance may also be defined as
where
Kendall tau distance can also be defined as the total number of discordant pairs.
Kendall tau distance in Rankings: A permutation (or ranking) is an array of N integers where each of the integers between 0 and N-1 appears exactly once.
The Kendall tau distance between two rankings is the number of pairs that are in different order in the two rankings. For example, the Kendall tau distance between 0 3 1 6 2 5 4 and 1 0 3 6 4 2 5 is four because the pairs 0-1, 3-1, 2-4, 5-4 are in different order in the two rankings, but all other pairs are in the same order.
If Kendall tau function is performed as formula_22 instead of formula_9 (where formula_1 and formula_2 are the rankings of formula_26 and formula_27 elements respectively), then triangular inequality is not guaranteed. The triangular inequality fails in cases where there are repetitions in the lists. So then we are not dealing with a metric anymore.
Example.
Suppose one ranks a group of five people by height and by weight:
Here person A is tallest and third-heaviest, and so on.
In order to calculate the Kendall tau distance, pair each person with every other person and count the number of times the values in list 1 are in the opposite order of the values in list 2.
Since there are four pairs whose values are in opposite order, the Kendall tau distance is 4. The normalized Kendall tau distance is
A value of 0.4 indicates that 40% of pairs differ in ordering between the two lists.
Computing the Kendall tau distance.
A naive implementation in Python (using NumPy) is:
import numpy as np
def normalised_kendall_tau_distance(values1, values2):
 """Compute the Kendall tau distance."""
 n = len(values1)
 assert len(values2) == n, "Both lists have to be of equal length"
 i, j = np.meshgrid(np.arange(n), np.arange(n))
 a = np.argsort(values1)
 b = np.argsort(values2)
 ndisordered = np.logical_or(np.logical_and(a[i] < a[j], b[i] > b[j]), np.logical_and(a[i] > a[j], b[i] < b[j])).sum()
 return ndisordered / (n * (n - 1))
However, this requires formula_29 memory, which is inefficient for large arrays.
Given two rankings formula_30, it is possible to rename the items such that formula_31. Then, the problem of computing the Kendall tau distance reduces to computing the number of "inversions" in formula_2—the number of index pairs formula_33 such that formula_34 while formula_35. There are several algorithms for calculating this number.
Here is a basic C implementation.
int kendallTau(short x[], short y[], int len) {
 int i, j, v = 0;
 bool a, b;
 for (i = 0; i < len; i++) {
 for (j = i + 1; j < len; j++) {
 a = x[i] < x[j] && y[i] > y[j];
 b = x[i] > x[j] && y[i] < y[j];
 if (a || b)
 v++;
 return abs(v);
float normalize(int kt, int len) {
 return kt / (len * (len - 1) / 2.0);