The Kendall Tau Distance For Permutations Example C# Code

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
This entry was posted in Miscellaneous. Bookmark the permalink.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s