The question is:
Given a sequence of positive integers A={1,2,3,...,N}.
Count the number of sequences you can get after making K swaps between adjacent element on it for a given N ?
My approach:
My algorithm to solve such a programming question is very naive. I could only think of making all the possible k swaps and then count the sequences.
Can anyone help me out with a better algorithm?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ I believe this is from an ongoing contest. Details: math.stackexchange.com/questions/839884/count-swap-permutations $\endgroup$– amWhyCommented Jun 20, 2014 at 14:40
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
I'll assume you mean that the $K$ swaps are between adjacent coordinates and carried out in sequence and not necessarily disjoint. For example, starting with $(1,2,\ldots,N)$, the first swap could be to interchange the 2nd and 3rd coordinates, the second swap could be to interchange the 4th and 5th coordinates, and the third swap could interchange the 3rd and 4th coordinate. Thus, the swaps are between adjacent elements, as you require, but the coordinates are not necessarily disjoint, and the order in which these swaps are carried out is important. Since you are looking for all sequences that can be obtained, starting from the sequence $(1,2,\ldots,N)$, using exactly $K$ adjacent swaps, you are actually looking for the number of vertices that can be reached in the bubble sort graph $BS(N)$, starting from any particular vertex, using a walk of length exactly $K$. The graph $BS(N)$ is the Cayley graph of the symmetric group $S_n$ generated by the set of $n-1$ adjacent transpositions $\{(1,2),(2,3),\ldots,(n-1,n)\}$. I don't know if any formula for this function $f(N,K)$ is known. You could carry out some simulations (using software packages such as GAP or SAGE, which have built-in functions to construct Cayley graphs and calculate distances between vertices) and determine if the numbers obtained are in OEIS.
$\begingroup$
$\endgroup$
Hint: By $K$ adjacent swaps I assume you mean that you choose a run of $2K$ numbers and swap each pair. So if $K=3$ we could wind up with $\{1,2,4,3,6,5,8,7,9,10\dots,N\}$ for example. If so, the result is determined by the first number, it doesn't matter the order you make the swaps.
answered Jun 19, 2014 at 20:36