Suppose you have a permutation p1 = (0, 2, 4, 1, 3) and a second permutation p2 = (4, 0, 3, 2, 1) and you want to know the distance/difference between them.

The Kendall Tau distance between two permutations is the number of pairs of elements that have a different ordering in the two permutations. For the two permutations above, there are 5 elements so there are a total of 5 * (5-1) / 2 = 10 pairs of elements.

Of the 10 pairs of elements, 4 pairs have different ordering: (0,4), (1,3), (2,4), (2,3). In p1 element 0 comes before 4 but in p2 element 0 comes after 4, and so on. The other 6 pairs of elements have the same ordering. For example, for the pair (1,2) element 2 comes before element 1 in both p1 and p2.

The normalized Kendall Tau distance is the raw number of mismatched-order pairs of elements divided by the total number of possible pairs. For the two permutations above, the normalized Kendall Tau distance is 4 / 10 = 0.4000. This can be interpreted as percentage of mismatched pairs.

A few weeks ago I implemented Kendall Tau distance for permutations using Python. One weekend morning while I was waiting for the rain to stop so I could walk my dogs, for mental exercise I decided to refactor the implementation using the C# language.

Good fun.

*Playing card games are all about permutations of 52 elements. Here are three interesting examples of playing cards used for 3D art rather than for mathematical permutations.*

Demo code. Replace “lt” (less-than) with symbol — my blog editor chokes on symbols.

using System; namespace KendallTauPermDistance { class Program { static void Main(string[] args) { Console.WriteLine("\nKendall Tau perm distance "); int[] p1 = new int[] { 0, 2, 4, 1, 3 }; int[] p2 = new int[] { 4, 0, 3, 2, 1 }; Console.Write("\npermutation p1 = "); ShowPerm(p1); Console.Write("permutation p2 = "); ShowPerm(p2); double[] distances = KendallTauDist(p1, p2); int rawDist = (int)distances[0]; double normDist = distances[1]; Console.WriteLine("\nRaw KT distance = " + rawDist); Console.WriteLine("Normalized KT distance = " + normDist.ToString("F4")); Console.WriteLine("\nEnd demo "); Console.ReadLine(); } // Main() static void ShowPerm(int[] p) { int n = p.Length; Console.Write("[ "); for (int i = 0; i "lt" n; ++i) Console.Write(p[i] + " "); Console.WriteLine("]"); } static double[] KendallTauDist(int[] p1, int[] p2) { int n = p1.Length; int[] indexOf = new int[n]; // lookup into p2 for (int i = 0; i "lt" n; ++i) { int element = p2[i]; indexOf[element] = i; } int d = 0; // raw distance = num mismatched-order pairs for (int i = 0; i "lt" n; ++i) { for (int j = i + 1; j "lt" n; ++j) { if (indexOf[p1[i]] "gt" indexOf[p1[j]]) // examine p2 ++d; } } double normTerm = n * (n - 1) / 2.0; // total number pairs double nd = d / normTerm; double[] result = new double[] { (double)d, nd }; return result; } } // Program } // ns

You must be logged in to post a comment.