# “Distance” between two permutations?

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 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!

• I am not entirely clear how you get $7$ in example c. All of your example give the metric relative to the identity element ... so you might be interested in the Coxeter presentation of the Symmetric group. groupprops.subwiki.org/wiki/… ... Sorry, rubbish reference, that wiki page needs some work ! – Donald Splutterwit Oct 27 '17 at 20:49
• I just did it by hand, not with any particular algorithm (in other words, 7 might be wrong). An example of the operations (where move(startIndex, endIndex) defines the move operation) would be: move(6, end), move(5, end), move(4, end)... move(0, end), which would be 7 operations. As for you suggestion, it seems similar to the suggestion in what I linked which relies on transposition of adjacent (or even non-adjacent) elements, which is missing the property of not "damaging" existing sequences which are already in order. Maybe that's a bad property to look for though... – user986122 Oct 27 '17 at 20:56
• You might want to check out the Kendall tau distance, which gives the number of pairs for which the two permutations disagree about which one comes earlier. That might satisfy your "don't penalize sublists in the wrong place" criterion: en.wikipedia.org/wiki/Kendall_tau_distance – Gregory J. Puleo Oct 27 '17 at 21:58
• Kendall tau is an awesome looking metric. It seems to balance the best properties of many of the metrics. It still doesn't handle reflection, but the more I think about it the more I think that property needs to be analyzed independently. Thank you! – user986122 Oct 30 '17 at 20:38

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."

• Very good suggestions, thank you. I think you're right about "swap" and "reversal" biasing my definition. I'm not sure if I would want a reversal to count as an operation or not (I'm not sure what the implication would be). As for moving sublists, I like that idea. I wonder though if I'd need a way to document how large the sublist that was moved was. For instance, I don't know if I'd want to count a move of [5,6,7,8] as the same as a move of [5,6] then a move of [7,8]. Great suggestions, thank you! – user986122 Oct 27 '17 at 21:02

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$. • I really like the approach with permutation matrices. It makes the issue of distance feel a bit more concrete. It drops the assumption about contiguous sublists being important, but in exchange it's a fairly straightforward metric. Out of curiosity, what did you use to do your visualization? I may want to try something similar when/if I show this method to my colleagues. – user986122 Oct 27 '17 at 22:23
• @user986122. Excel, with conditonal formating. – keepAlive Oct 27 '17 at 22:25