# Probability of Correctly Ordering Items Within a Limited Number of Moves

I have a question related to permutations and probability. Suppose we have 6 distinct items that we want to arrange in a specific order. We start with the items in some arbitrary order, and we can make a "move" by swapping the positions of any two items.

Given that we can make up to N (for n in [1,2,3,4,5,6]) moves, what is the probability that we can achieve the correct order of items? Assume that each possible ordering is equally likely.

To clarify, a "move" is defined as swapping the positions of two items. So N=2 means we can swap two such swaps. The "correct" order is a specific predetermined order of the items.

I understand that the total number of possible orderings is 6!, or 720. However, I'm not sure how to calculate the number of orderings that can be reached within N moves, or how to translate this into a probability. Any insights would be appreciated.

• It looks like you meant to say that $N = 2$ means we can do up to two such swaps. Jul 3, 2023 at 0:07
• It appears to me that it requires $k-1$ swaps to realize a $k$-cycle, which should help the calculation a lot. Jul 3, 2023 at 0:15

As Robert Shore indicates in his comment, if a permutation, $$\ p\$$, is a product of $$\ c\$$ disjoint cycles of lengths $$\ \ell_1,\,\ell_2,\,\dots,\,\ell_c\$$, then it can be expressed as a product of $$\ n_p=\sum_\limits{j=1}^c\big(\ell_j-1\big)\$$ transpositions, but not as a product of any smaller number of transpositions. Thus, $$\ n_p\$$ is the smallest number of swaps needed to return a sequence of numbers that has been permuted by $$\ p\$$ back to its original order. The following table lists the $$\ 11\$$ possible cycle structures of the permutations on $$\ \{1,2,3,4,5,6\}\$$, the number of permutations with that cycle structure, the probability of a random permutation having that cycle structure and the minimum number of transpositions whose product can be equal to a permutation with that cycle structure. The notation $$\ c_1\times\ell_1+c_2\times\ell_2+\dots+c_r\times \ell_r\$$ used in the second column of the table indicates a cycle structure comprising $$\ c_i\$$ cycles of length $$\ \ell_i\$$ for each $$\ i=1,2,\dots,r\$$. $$\begin{array}{|c|c|c|c|c|} \hline {\ \\\text{index }\ i}&{\hspace{1.5em}\text{cycle}\\{\text{structure}\ s_i}}&{\hspace{1.5em}\text{number of}\\\text{permutations }\ n_i}&{\ \\\text{probability }\ \pi_i}&{\hspace{1.5em}\text{number of}\\\text{transpositions }\ t_i}\\ \hline 1&6\times1&1&\frac{1}{720}&0\\ \hline 2&4\times1+1\times2&{6\choose2}=15&\frac{15}{720}=\frac{1}{48}&1\\ \hline 3&2\times1+2\times2&\frac{1}{2}{6\choose2}{4\choose2}=45&\frac{45}{720}=\frac{1}{16}&2\\ \hline 4&3\times2&\frac{1}{6}{6\choose2}{4\choose2}=15&\frac{15}{720}=\frac{1}{48}&3\\ \hline 5&3\times1+1\times3&2{6\choose3}=40&\frac{40}{720}=\frac{1}{18}&2\\ \hline 6&1\times1+1\times2+1\times3&2{6\choose3}{3\choose2}=120&\frac{120}{720}=\frac{1}{6}&3\\ \hline 7&2\times3&2{6\choose3}=40&\frac{40}{720}=\frac{1}{18}&4\\ \hline 8&2\times1+1\times4&3!{6\choose4}=90&\frac{90}{720}=\frac{1}{8}&3\\ \hline 9&1\times2+1\times4&3!{6\choose4}=90&\frac{90}{720}=\frac{1}{8}&4\\ \hline 10&1\times1+1\times5&4!{6\choose5}=144&\frac{144}{720}=\frac{1}{5}&4\\ \hline 11&1\times6&5!=120&\frac{120}{720}=\frac{1}{6}&5\\ \hline \end{array}$$

Thus, the probabilities that a random permutation of $$6$$ objects can be restored with at most $$\ n\$$ swaps is given by the following table.

$$\begin{array}{|c|c|c|c|c|c|c|} \hline n&5&4&3&2&1&0\\ \hline {\text{probability that }\ n\\ \text{swaps will suffice}}&1&\sum_\limits{i=1}^{10}\pi_i=\frac{5}{6}&{\pi_8+\sum_\limits{i=1}^6\pi_i\\\hspace{1em}=\frac{163}{360}}&{\pi_6+\sum_\limits{i=1}^4\pi_i\\\hspace{1em}=\frac{101}{720}}&\pi_1+\pi_2=\frac{1}{45}&\pi_1=\frac{1}{720}\\ \hline \end{array}$$

Robert Shore's comment is on point. For a given permutation with cycle lengths $$K_1, K_2, \dots, K_M$$, where $$M$$ is the number of cycles, the number of swaps you need to reach the identity permutation is $$\sum_{i=1}^M (K_i-1)$$, which is the same as $$N-M$$.

To see this, you can check that any swap either increases or decreases this distance by $$1$$ (and there is always a way to decrease it, unless you are already at the identity permutation).

For a uniformly random permutation, when $$N$$ is large, the number of cycles $$M$$ is roughly Poisson with mean $$\log(N)$$, with fluctuations on the scale of $$\sqrt{\log(N)}$$. You can find a ton of different discussions about this quantity, for instance:

So the number of swaps you need for a uniformly random permutation is $$N-\log(N)\pm O(\sqrt{\log(N)})$$.

From a given permutation, one move that is guaranteed to reduce the distance is to move element $$i$$ to position $$i$$ (where $$i$$ is any element that is currently out of position). So for example, you have the following explicit algorithm to get to the identity in minimum time:

for $$i=1$$ to $$N-1$$:

• if element $$i$$ is not in position $$i$$, swap $$i$$ with the element at position $$i$$.

You can understand the $$\log(N)$$ nicely in terms of this algorithm. It turns out that after step $$i$$, the permutation of items $$\{i+1, \dots, N\}$$ is uniformly random. In particular, the event $$B_i$$ that a swap is not required at step $$i$$ has probability $$1/(N-i)$$. (In fact, these events $$(B_i)_{1\leq 1\leq N-1}$$ are independent.) The expected number of steps at which a swap is not required is then $$1/N+1/(N-1)+\dots+1/3+1/2$$ which grows like $$\log(N)$$.