<s>[INST] Logic for decomposing a permutation into different products composed of transpositions I know that any permutation cycle can be decomposed into transpositions as follows:

$(a_1,a_2...,a_n) = (a_1,a_{n-1})...(a_1,a_2)$

But in my book there is an example of the following form

$(1,2,3,4,5) = (5,4)(5,2)(2,1)(2,5)(2,3)(1,3)$

I verified that it holds true. But I cant seem to figure out how the author came up with that. Also, What is the generic algorithm to produce all decompositions of permutation in terms of transpositions.
 [/INST] In his question and comments the OP keeps asking HOW did the author of his book come up with
$\tag a  \sigma = (1,2,3,4,5) = (5,4)(5,2)(2,1)(2,5)(2,3)(1,3)$
But we have the transposition algebra rules:
\begin{align}(1) \quad (ab)(ab)&=1_{Id}\\
(2) \quad (ab)(cd)&=(cd)(ab)\\
(3) \quad (ab)(bc)&=(ca)(ab)\\
(4) \quad (ab)(bc)&=(bc)(ca)\end{align}
The first identity (1) can be used to expand a product of $n$ transpositions into another one with length $n+2$ - you can always employ this 'silly padding'. The other manipulations (2) thru (4) can be used to 'disguise' this 'silly padding'.
Observe that given a product of transpositions we can, step by step, 'move' any fixed transposition to a new position in the composition product, but other transpositions might have to be modified along the way.
Since $2$ occurs $4$ times in $(5,4)(5,2)(2,1)(2,5)(2,3)(1,3)$ we write
$\quad (1,2,3,4,5) = (3,4,5,1,2) = (2, 1) (2, 5) (2, 4) (2, 3) =$
$\quad \quad  (5 ,4) (5 ,4) (2, 1) (2, 5) (2, 4) (2, 3) (1,3) (1,3) =$
$\quad \quad  (5 ,4) (5 ,4) (2, 5) (5, 1) (2, 4) (1, 2) (2,3) (1,3) =$
$\quad \quad  (5 ,4) (5 ,2) (2, 4) (5, 1) (2, 4) (1, 2) (2,3) (1,3) =$
$\quad \quad  (5 ,4) (5 ,2)  (5, 1)  (1, 2) (2,3) (1,3) =$
$\quad \quad  (5 ,4) (5 ,2)  (2, 1)  (2, 5) (2,3) (1,3) $
</s>