2. Permutation Swaps #

Created Sunday 26 July 2020

Question

• We are given a permutation P, of numbers from 1 to n. Some of the places can be flipped, as many times as required.
• We are given another permutation Q. Same rules.
• We need to answer if P ↔ Q by doing flips.

Answer

1. Change the representation from string to graph.
2. If all components are connected, then equivalence may be possible.
3. But if the components are disjoint, then equivalence is impossible.
4. So we’ll find the connected components and show that they are equivalent to the other permutations, this way we prove that the graphs are equivalent.