×

SWPERMS - Editorial

Contest
Practice

PROBLEM:

A permutation P= (p[1], p[2], ..., p[n]) of (1, 2, ..., n) is written on a blackboard. You have m pairs of integers (x_i, y_i). At any stage you can choose a pair (x, y) and swap the values of p[x] and p[y] (note that P is still a permutation after this operation). Initially P= (1, 2, ..., n). Find the number of different permutations you can obtain after finite number of operations.

TL;DR:

Consider an undirected graph with vertices 1, 2, ..., n where there is an edge between x and y for each given pair (x, y). 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)!$

FULL SOLUTION:

Let's consider the graph where the vertices are labelled 1, 2, ..., n and pairs are edges. Note that swapping a pair (x, y) is equivalent to switching the labels of the vertices across the corresponding edge.

Observation 1: If there is no path from u to v in this graph, it is not possible to get a permutation P where P[u]= v.
Proof: Suppose otherwise that it is possible to apply the swaps in some order that the label of vertex u is at the position of vertex v . Let $t_1, t_2, ..., t_k$ be the successive vertices with which u 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 u to v. Contradiction.

From observation 1, we find out that if u and v 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 i'th component can be permuted, then the answer will be simply $f(1) \cdot f(2) \cdots f(t)$ where t is the number of connected components.

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 k can be attained. Note that this is equivalent to proving that if the graph is connected, all $n!$ permutations are achievable.

Claim: If the graph is connected, all permutations of 1, 2, ..., n can be obtained.
Proof: There are probably multiple ways to prove this. Here's a simple one. We'll prove that for all u≠v, it is possible to apply the swaps in such a way that the positions of all other elements are unchanged and those of u and v are interchanged. Since the graph is connected, there exists a simple path $t_1, t_2, ..., t_k$ from u to v. Apply the operations $u-t_1, t_1-t_2, ...., t_{k-1}-t_k, t_k-v$ - this brings the label of u to the position of v and the label of v 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 u and v were interchanged. Thus we can always say (u, v) 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.

This claim shows that the number of permissible permutations of the i'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 t is the number of connected components. This can be found in O(m+n) with a plain dfs.

This question is marked "community wiki".

15718
accept rate: 10%

19.7k350498541

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,480
×3,705
×921
×23
×5
×1

question asked: 01 Mar '16, 01:58

question was seen: 664 times

last updated: 04 Mar '16, 21:52