Swap Distance (Q7361034)

Given two lists that are permutations of one another, the swap distance (also known as the Kendall tau distance ) is the minimum number of swap operations of adjacent elements required to make the two lists the same. Equivalently, the swap distance of two finite linear orders $\preceq$ and $\unlhd$ is the number of disagreements of the two orders, i.e. of pairs $(x,y)$ such that $x\prec y$ and $y\lhd x$. This article defines these two notions of swap distance as well as their equivalence under the obvious isomorphism between lists and linear orders given by interpreting a list as a ranking of elements in descending order. An efficient $O(n\log n)$ algorithm to compute the swap distance is also provided via the connection to the number of inversions of a list, for which an efficient algorithm is already available in the AFP.