Neighboring transpositions for number of length n, Kendall Tau Distance I have the following question: Given is a string (or number) of length n, n being the number of its digits (or characters) - say for instance given is the number "12345" which has length n = 5.
"Swaps" are now defined as the change in the order of two neighboring digits: For instance going from 12345 to 12435 would require one swap. 
For a number of length 5 (or more general n) what would be the maximal number of swaps between this number and a permutation of the number? 
By this I obviously mean the biggest minimal number of swaps (I would not swap two neighboring digits and then swap them back and so forth).
As I understand it, the Kendall Tau Distance is measuring exactly this distance, so another way to formulate the question would be to ask for the maximal Kendall Tau Distance between a number of length n and a permutation of it.
 A: In this answer I try to solve the problem using group theory. Let :
$$\mathcal{S}(n):=\{f:\{1,...,n\}\rightarrow \{0,...,9\}\} $$
This is the set of string of $n$ digits. Then you have a $\mathfrak{S}_n$ (group of permutations of $\{1,...,n\}$) action on $\mathcal{S}(n)$ given by :
$$[\sigma.f](i):=f(\sigma^{-1}(i)) $$
Now let $d$ be the Kendall Tau Distance on $\mathcal{S}(n)$ I would define it like this :
$$d(f,g)=\infty\text{ if } g\neq\sigma.f\text{ for any } \sigma\in\mathfrak{S}_n $$
That is if  $g$ cannot be reached by permutations of digits of $f$ and :
$$d(f,g)=min\{r|f=(\tau_1...\tau_r).g\text{ and } \tau_i\text{ are transpositions}\}\text{ if } g=\sigma_0.f\text{ for some } \sigma_0\in\mathfrak{S}_n $$
If $g=\sigma_0.f$ then it is clear that $min\{r|g=(\tau_1...\tau_r).f\text{ and } \tau_i\text{ are transpositions}\}$ exists because $\sigma_0$ can be written as a product of transpositions.
Now a remark, a cycle of length $r$ can be minimally written as a product of $r-1$ transpositions (it is not hard to show this) and if $\sigma_1$ and $\sigma_2$ are disjoint supports permutations then the minimal number of transpositions needed to write $\sigma_1\sigma_2$ is equal to the sum of the minimal numbers for $\sigma_1$ and $\sigma_2$. Hence if we write :
$$\sigma=c_1...c_q $$
As a product of disjoint support cycles (it is unique) where $c_i$ is a cycle of length $l_i$ (it might be $1$) then  we have that the minimal number of transposition to write $\sigma$ will be :
$$t(\sigma):=l_1-1+...+l_q-1=\sum_{i=1}^q(l_i-1)=n-q$$
Hence for any $\sigma$ the $t(\sigma)$ depends only on the number of disjoint cycles in the decomposition of $\sigma$. The good thing about it, is that it is easy to compute.
Now another way to write the Kendal Tau Distance is the following :
$$d(f,g)=min\{t(\sigma)|g=\sigma.f\} $$
Where the min of $\emptyset$ is defined to be $\infty$. Hence (when this has a meaning, i.e. the distance between $f$ and $g$ is finite) :
$$d(f,g)=n-max\{q|g=\sigma.f\text{ and } \sigma \text{ has } q\text{ cycles in its decomposition}\} $$
Now the last thing to do is to determine the set of $\sigma$ such that $\sigma.f=g$. Assume you are given a $\sigma_0\in\mathfrak{S}_n$ such that $g=\sigma_0.f$ then I claim that :
$$\{\sigma\in\mathfrak{S}_n|\sigma.f=g\}=\sigma_0Stab(f) $$
This is easy to show. Finally, you must compute all the elements in $Stab(f)$, I claim that :
$$Stab(f)=\mathfrak{S}_{f^{-1}(0)}\times ...\times \mathfrak{S}_{f^{-1}(9)} $$
Hence for small values of $n$ the group $Stab(f)$ won't be too big. Hence you can compute the number of cycles in the disjoint cycle decomposition for any $\sigma_0\sigma$ where $\sigma\in Stab(f)$ and this gives you the distance by :
$$d(f,g)=n-max\{q|g=\sigma.f\text{ and } \sigma \text{ has } q\text{ cycles in its decomposition}\} $$
