ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 15 Apr 2022 18:12:03 +0200permutations and transpositionshttps://ask.sagemath.org/question/61985/permutations-and-transpositions/How a permutation be converted to a product of transpositions. inversions() gives an incorrect anser.
P=Permutation([4, 8, 3, 1, 9, 2, 6, 7, 5]); P.inversions()
[(1, 3),(1, 4),(1, 6),(2, 3),(2, 4),(2, 6),(2, 7),(2, 8),(2, 9),(3, 4),(3, 6),(5, 6),(5, 7),(5, 8),(5, 9),(7, 9),(8, 9)]
I expect
[(1,3),(1,4),(2,3),(2,4),(2,6),(2,7),(2,8),(3,6),(5,9)]Fri, 15 Apr 2022 15:22:33 +0200https://ask.sagemath.org/question/61985/permutations-and-transpositions/Comment by Max Alekseyev for <p>How a permutation be converted to a product of transpositions. inversions() gives an incorrect anser.</p>
<pre><code>P=Permutation([4, 8, 3, 1, 9, 2, 6, 7, 5]); P.inversions()
[(1, 3),(1, 4),(1, 6),(2, 3),(2, 4),(2, 6),(2, 7),(2, 8),(2, 9),(3, 4),(3, 6),(5, 6),(5, 7),(5, 8),(5, 9),(7, 9),(8, 9)]
</code></pre>
<p>I expect</p>
<pre><code>[(1,3),(1,4),(2,3),(2,4),(2,6),(2,7),(2,8),(3,6),(5,9)]
</code></pre>
https://ask.sagemath.org/question/61985/permutations-and-transpositions/?comment=61988#post-id-61988See https://ask.sagemath.org/question/58820/permutations-and-transpositions/Fri, 15 Apr 2022 15:59:03 +0200https://ask.sagemath.org/question/61985/permutations-and-transpositions/?comment=61988#post-id-61988Answer by Max Alekseyev for <p>How a permutation be converted to a product of transpositions. inversions() gives an incorrect anser.</p>
<pre><code>P=Permutation([4, 8, 3, 1, 9, 2, 6, 7, 5]); P.inversions()
[(1, 3),(1, 4),(1, 6),(2, 3),(2, 4),(2, 6),(2, 7),(2, 8),(2, 9),(3, 4),(3, 6),(5, 6),(5, 7),(5, 8),(5, 9),(7, 9),(8, 9)]
</code></pre>
<p>I expect</p>
<pre><code>[(1,3),(1,4),(2,3),(2,4),(2,6),(2,7),(2,8),(3,6),(5,9)]
</code></pre>
https://ask.sagemath.org/question/61985/permutations-and-transpositions/?answer=61992#post-id-61992This 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)
Fri, 15 Apr 2022 16:55:34 +0200https://ask.sagemath.org/question/61985/permutations-and-transpositions/?answer=61992#post-id-61992Comment by Max Alekseyev for <p>This can be done via reduced words:</p>
<pre><code>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)
</code></pre>
https://ask.sagemath.org/question/61985/permutations-and-transpositions/?comment=61995#post-id-61995Yes, since it uses adjacent transpositions.Fri, 15 Apr 2022 18:12:03 +0200https://ask.sagemath.org/question/61985/permutations-and-transpositions/?comment=61995#post-id-61995Comment by tmonteil for <p>This can be done via reduced words:</p>
<pre><code>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)
</code></pre>
https://ask.sagemath.org/question/61985/permutations-and-transpositions/?comment=61994#post-id-61994Note that this decomposition is pretty long:
sage: q
[(3, 4),
(2, 3),
(1, 2),
(7, 8),
(6, 7),
(5, 6),
(4, 5),
(3, 4),
(2, 3),
(4, 5),
(3, 4),
(8, 9),
(7, 8),
(6, 7),
(5, 6),
(7, 8),
(8, 9)]
sage: len(q)
17Fri, 15 Apr 2022 17:13:48 +0200https://ask.sagemath.org/question/61985/permutations-and-transpositions/?comment=61994#post-id-61994Answer by tmonteil for <p>How a permutation be converted to a product of transpositions. inversions() gives an incorrect anser.</p>
<pre><code>P=Permutation([4, 8, 3, 1, 9, 2, 6, 7, 5]); P.inversions()
[(1, 3),(1, 4),(1, 6),(2, 3),(2, 4),(2, 6),(2, 7),(2, 8),(2, 9),(3, 4),(3, 6),(5, 6),(5, 7),(5, 8),(5, 9),(7, 9),(8, 9)]
</code></pre>
<p>I expect</p>
<pre><code>[(1,3),(1,4),(2,3),(2,4),(2,6),(2,7),(2,8),(3,6),(5,9)]
</code></pre>
https://ask.sagemath.org/question/61985/permutations-and-transpositions/?answer=61989#post-id-61989First, 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
TrueFri, 15 Apr 2022 15:59:33 +0200https://ask.sagemath.org/question/61985/permutations-and-transpositions/?answer=61989#post-id-61989