2
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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}\} $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .