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