Splitting permutations into transpositions
One way to do it consists of two steps:


Find the cycle representation of the input.
Convert the cycle representation into a product of transpositions.


The first step is very similar to DFS. The second step is an exercise in permutation group theory.