permutations and transpositions

edit

This can be done via reduced words:

P = Permutation([4, 8, 3, 1, 9, 2, 6, 7, 5])
r = P.reduced_word()
q = [(i,i+1) for i in r]
assert prod(Permutation(str(i)) for i in q[::-1]) == P
print(q)

First, note that the image of 1 is 4, the image of 6 is 2:

sage: P(1)
4
sage: P(6)
2
sage: P(6) < P(1)
True

Hence, (1,6) should be part of the inversions (an inversion is a pair (i,j) such that i<j and P(i)>P(j)).

Now, if you want to decompose a permutations into transpositions, note that there are many ways, none of them is canonical. However, you can decompose your permutation into disjoint cycles and then each cycle can be decomposed into transpositions.

sage: C = P.cycle_tuples() ; C
[(1, 4), (2, 8, 7, 6), (3,), (5, 9)]

From such a decomposition, you can easily get a decomposition of the permutation into tuples (because (a1,a2,a3,...,an) = (a1,a2)(a1,a3)...(a1,an)) :

sage: L = []
....: for c in C:
....:     if len(C) >= 2:
....:         a = c[0]
....:         for b in c[1:]:
....:             L.append((a,b))

sage: L
[(1, 4), (2, 8), (2, 7), (2, 6), (5, 9)]

You can check:

sage: prod(Permutation(t) for t in L)
[4, 8, 3, 1, 9, 2, 6, 7, 5]

sage: prod(Permutation(t) for t in L) == P
True