Distance between two ordered sets Is there a way to measure the "distance" between two ordered sets?
Say i got two sequences of letters:
$$
S_1  \{A, B, C, D, E, F\}
$$
$$
S_2  \{B, C, D, A, F, E\}
$$
How could I find an "amount of difference" between $S_1$ and $S_2$?
Is there some generic metric on a space of ordered sets?
 A: There are different ways to do that. You could use euclidean distance (or any other metric applicable to vector spaces) if the alphabet is in a metric space. As a special case if you use $L^1$ distance and your alphabet is ${0, 1}$ with usual metric you will get the hamming distance.
Since you're talking permutation distance, then yes it's a metric too given that you use the least number of exchanges to go from one permutation to the next. In your example I'd guess that the distance would be $4$ (swap A-B, A-C, A-D and then E-F, my guess is that this is the least amount of swaps you could do to get to $S_2$). It's obvious that the axioms of metric is fulfilled:


*

*Since both $a$ and $b$ can be expressed as a number of swaps from the identity map ($I$) and therefore theres a way from $I$ to $a$ and $I$ to $b$ (and reversing that makes a way from $b$ to $I$) you have a way from $b$ to $a$ via $I$ - at least one way makes for a shortest way. That is for each $b$ and $a$ theres a $d(b,a)$ being the lowest number of swaps to get from $b$ to $a$.

*$d(a,b) \ge 0$ (you can't swap a negative number of times so the minimum of swaps has to be non-negative)

*$d(a,b) = 0 \Rightarrow a=b$ (if you can get from $a$ to $b$ without swaps then they have to be the same)

*$d(a,b) = d(b,a)$ (you can get from $b$ to $a$ with the same swaps in reverse order as those that take you from $a$ to $b$, that is the same number of steps - the minimum of those has to be the same)

*$d(a,b) + d(b, c) \ge d(a,c)$ (you can get from $a$ to $c$ by using the $d(a,b)$ steps from $a$ to $b$ and the $d(b,c)$ steps from $b$ to $c$, the minimum number of steps from $a$ to $c$ can't be greater than that.

