Answers to: SWPERMS - Editorialhttps://discuss.codechef.com/questions/79746/swperms-editorial<p></p><h2>Problem link:</h2> <a href="https://www.codechef.com/IPC15P3A/problems/SWPERMS">Contest</a> <br> <a href="https://www.codechef.com/problems/SWPERMS">Practice</a> <p></p>
<p></p><h2>PROBLEM:</h2><p></p>
<p>A permutation <b>P= (p[1], p[2], ..., p[n])</b> of <b>(1, 2, ..., n)</b> is written on a blackboard. You have <b>m</b> pairs of integers <b>(x_i, y_i)</b>. At any stage you can choose a pair <b>(x, y)</b> and swap the values of <b>p[x]</b> and <b>p[y]</b> (note that <b>P</b> is still a permutation after this operation). Initially <b>P= (1, 2, ..., n)</b>. Find the number of different permutations you can obtain after finite number of operations.
<br><br> </p> <p> </p><h2>TL;DR:</h2> <p>
Consider an undirected graph with vertices <b>1, 2, ..., n</b> where there is an edge between <b>x</b> and <b>y</b> for each given pair <b>(x, y)</b>. Let $c_1, c_2, \cdots , c_t$ be the sizes of the connected components of this graph. The answer will be $(c_1)!\cdot (c_2)! \cdots (c_t)!$
<br> <br> </p> <p> </p><h2> FULL SOLUTION: </h2> <p>
Let's consider the graph where the vertices are labelled <b>1, 2, ..., n</b> and pairs are edges. Note that swapping a pair <b>(x, y)</b> is equivalent to switching the labels of the vertices across the corresponding edge. <br> <br>
<b>Observation 1:</b> If there is no path from <b>u</b> to <b>v</b> in this graph, it is not possible to get a permutation <b>P</b> where <b>P[u]= v</b>. <br>
<b>Proof:</b> Suppose otherwise that it is possible to apply the swaps in some order that the label of vertex <b>u</b> is at the position of vertex <b>v</b> . Let $ t_1, t_2, ..., t_k$ be the successive vertices with which <b>u</b> was swapped- this means the edges $u-t_1, t_1-t_2, \cdots , t_{k-1}-t_k$ and $t_k-v$ are all present in our graph, i.e. there is a path from <b>u</b> to <b>v</b>. Contradiction. <br> <br></p>
<p>From observation 1, we find out that if <b>u</b> and <b>v</b> are in different connected components their positions cannot be interchanged. We can now treat each connected component separately. Let $f(i)$ be the number of ways the <b>i</b>'th component can be permuted, then the answer will be simply $f(1) \cdot f(2) \cdots f(t)$ where <b>t</b> is the number of connected components.</p>
<p>Now we shall prove that all possible permutations of a component can be obtained after finitely many operations, i.e. all $k!$ permutations of a connected component of size <b>k</b> can be attained. Note that this is equivalent to proving that if the graph is connected, all $n!$ permutations are achievable. <br> <br></p>
<p><b>Claim:</b> If the graph is connected, all permutations of <b>1, 2, ..., n</b> can be obtained. <br>
<b>Proof:</b> There are probably multiple ways to prove this. Here's a simple one. We'll prove that for all <b>u≠v</b>, it is possible to apply the swaps in such a way that the positions of all other elements are unchanged and those of <b>u</b> and <b>v</b> are interchanged. Since the graph is connected, there exists a simple path $t_1, t_2, ..., t_k$ from <b>u</b> to <b>v</b>. Apply the operations $u-t_1, t_1-t_2, ...., t_{k-1}-t_k, t_k-v$ - this brings the label of <b>u</b> to the position of <b>v</b> and the label of <b>v</b> to the position of $t_k$. Apply the operations $t_k-t_{k-1}, t_{k-1}-t_{k-2}, ..., t_1-u$ again- now all other labels are at their original positions and those of <b>u</b> and <b>v</b> were interchanged. Thus we can always say <b>(u, v)</b> is one of the pairs given to us (even though it isn't)- because there exists a sequence of allowed operations which has the exact same effect. Now we can simply claim to have all $\binom{n}{2}$ pairs available and it's easy to get to the conclusion. <br> <br></p>
<p>This claim shows that the number of permissible permutations of the <b>i</b>'th connected component is $(c_i)!$ where $c_i$ is its size. Thus, the answer is $(c_1)! \cdot (c_2) ! \cdots (c_t)!$ where <b>t</b> is the number of connected components. This can be found in <b>O(m+n)</b> with a plain dfs.</p>enTue, 26 Mar 2019 06:33:42 -0000