"Distance" between two permutations?

Question

I've been trying to find a 'good' definition of the "distance" between two permutations that matches my intuition. I found this post which gets part of the way to what I'm thinking about, but I don't think it gets there entirely. I'm very open to suggestions on distance metrics, but I came up with one that I'm not very attached to and would like some opinions.

The one I've thought would be helpful for me is based on a particular operation which I'm calling a "move" (I'm sure it has a real name, but I haven't found it while Googling), which I'm defining as a deletion followed by an insertion of the deleted element. For instance, if I have the sequence [4, 1, 2, 3] which I'm comparing to [1,2,3,4], I could delete 4 (at index 0) and insert 4 (at the end) and I would have performed 1 "move". In this way, the distance between [1,2,3,4] and [4,1,2,3] would be defined as 1.

Another example:

dist([1,2,3,4], [4,2,1,3]) = 2, because [4,2,1,3]->[4,1,2,3]->[1,2,3,4]

The reason I like this particular distance metric is because it doesn't penalize sublists which are simply in the wrong part in the sequence (but in the right order as a sublists). The thing I don't love about it is for longer lists, sometimes the answers don't intuitively match what I'm looking for - example:

a) dist([1,2,3,4,5,6,7,8], [5,6,7,8,1,2,3,4]) = 4
b) dist([1,2,3,4,5,6,7,8], [1,3,2,5,4,7,6,8]) = 3
c) dist([1,2,3,4,5,6,7,8], [8,7,6,5,4,3,2,1]) = 7

Intuitively, it seems like c and a should be "closer" to the left sequence than b, but this definition gives the opposite result.

At this point, the "distance" between two permutations is an ill defined concept to me, but I haven't found a metric that gives me an intuitive distance yet, so I'd love some opinions.

Edit:

For anyone who runs into this. The options people suggested below were great. The one I ended up deciding was best is the Kendall Tau Correlation (also see Kendall Tau distance). Although it doesn't generally forgive contiguous sequences which are grossly out of order, it has the fantastic property of giving negative correlations for reverse sequences and positive for forward sequences. It also gives some fairly intuitive answers overall (with the exception of not accounting for contiguity).

As an experiment, I also wanted to determine for a length 8 sequence (like what I've been using as examples), how much resolution does each measure give us? I.e., how many different distances does each option provide. So I ran all permutations of each of the discussed methods (with some minor modifications described below) and generated this histogram table. One final note of why Kendall Tau could be the overall winner is that you can actually weight the relative position exchanges, giving even more granularity in the distance result (as you'll see in the histograms).

Kendall Tau is computed via the python, scipy.stats library (as is the Weighted Tau). Note that weighted tau with all 1 weights is the same as traditional tau. The documentation for the weighted function also suggests that, in general, a hyperbolic function for the weights can be preferable. I also show what a linear weighting looks like though (i.e. 1,2,3,4,5,6,7,8 as the weights).

Finally, Transposition Distance is the distance metric described in the original post I linked.

Cycle Rearrangement Distance is the distance metric suggested by David K, allowing for contiguous movements and counting how many moves of contiguous blocks are needed to get to a particular configuration.

L1 Distance is the sum of the absolute value of the subtraction of each element in each list. I.e. sum(|[1,2,3] - [3,2,1]|)=4.

L0 Distance (for lack of a better term) is the method described by Kanak without the extra diagonal.

As you can see from the image, even without the weighting, Kendall Tau gives far more potential distances and has far more resolution than the other methods. Although I can imagine circumstances where the others would be preferred, that is the one I will be going forward with.

Thanks for all the help!

Answer 1

What about involving (some sort of) $\text{L}^1$-norms of permutation matrices?

Let's create $3$ of such matrices, with each corresponding to the three cases a), b) and c), respectively $\pi_a$, $\pi_b$ and $\pi_c$. With $v$ standing for the $8 \times 1$ vector equal to $(1,2,3,4,5,6,7,8)'$, what follows is my suggestion

It considers as distance the sum of off-diagonal $1$s. Like David, "To my eye" the cases $v_c$ "looks like an extreme opposite" of $v$. However, $v_a$ is as far as $v_c$ from $v$. The closest one is $v_b$.

---

To comply with your intuition about the proximity between $v$ and $v_c$, one may want to drop out from our sum the $1$s being on the ante-diagonal, giving a problematic distance of $0$. That of $v_b$ from $v$ becomes $4$.

---

Using your first example, the distance that one obtains is $2$.

Answer 2

In at least one way, your metric does penalize sublists that are in the wrong part of the sequence: a misplaced sublist of $n$ consecutive objects can add $n$ times as much to the "distance" as a single misplaced object, because you have to "move" $n$ objects from the misplaced sublist. It doesn't actually matter that the objects in the sublist were consecutive.

That's how your list $[5,6,7,8,1,2,3,4]$ ends up at distance $4$ from $[1,2,3,4,5,6,7,8],$ the same distance as from $[1,2,3,4,5,6,7,8]$ to $[5,1,6,2,7,3,8,4].$

Perhaps instead of moving individual objects, you want a single "move" to be able to move an entire sublist. That is, to convert $[5,6,7,8,1,2,3,4]$ to $[1,2,3,4,5,6,7,8]$ you can just take the sublist $[5,6,7,8]$ and move it to the end, so the distance is $1.$

I'm not sure why you would think $[8,7,6,5,4,3,2,1]$ should be "close" to $[1,2,3,4,5,6,7,8].$ To my eye it looks like an extreme opposite, although if you measured distance by counting swaps of objects (take two object out, leaving open space where they came from, then put each object into the other object's space), the distance would only be $4.$ Perhaps you want to count the reversal of a sublist (up to the length of the entire list) as a single "move."