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.Thu, 28 Mar 2013 16:23:31 +0100Finding the permutation that sorts a listhttps://ask.sagemath.org/question/9948/finding-the-permutation-that-sorts-a-list/Given a list (say, of numbers) `L`, the method `L.sort()` will put its elements in order. The function `sorted(L)` returns a new list with the elements of `L` in order. I would like a version of `sorted` that will not return the elements of `L` in sorted order, but rather, the *permutation* that puts them in sorted order. Does this exist in Sage? Thanks.Wed, 27 Mar 2013 19:44:08 +0100https://ask.sagemath.org/question/9948/finding-the-permutation-that-sorts-a-list/Answer by DSM for <p>Given a list (say, of numbers) <code>L</code>, the method <code>L.sort()</code> will put its elements in order. The function <code>sorted(L)</code> returns a new list with the elements of <code>L</code> in order. I would like a version of <code>sorted</code> that will not return the elements of <code>L</code> in sorted order, but rather, the <em>permutation</em> that puts them in sorted order. Does this exist in Sage? Thanks.</p>
https://ask.sagemath.org/question/9948/finding-the-permutation-that-sorts-a-list/?answer=14698#post-id-14698IIUC, the `numpy` library has a routine to do this already:
sage: L = [2,3,1,6,8,-3,9]
sage: numpy.argsort(L)+1
array([6, 3, 1, 2, 4, 5, 7])
Alternatively, you can use a Schwartzian transform (a.k.a. the "decorate-sort-undecorate" idiom). Starting from our list, we can enumerate it, counting from 1 (the "decorate" part)
sage: list(enumerate(L, 1))
[(1, 2), (2, 3), (3, 1), (4, 6), (5, 8), (6, -3), (7, 9)]
Sort these by the second term, the value:
sage: sorted(enumerate(L, 1), key=lambda x: x[1])
[(6, -3), (3, 1), (1, 2), (2, 3), (4, 6), (5, 8), (7, 9)]
Extract the sorted indices:
sage: ii = [pair[0] for pair in sorted(enumerate(L, 1), key=lambda x: x[1])]
sage: ii
[6, 3, 1, 2, 4, 5, 7]
Finally, we can make this into a proper `Permutation`:
sage: Permutation(ii)
[6, 3, 1, 2, 4, 5, 7]
sage: Permutation(ii).to_cycles()
[(1, 6, 5, 4, 2, 3), (7,)]
and confirm it by applying it to our list:
sage: P = Permutation(ii)
sage: P.action(L)
[-3, 1, 2, 3, 6, 8, 9]
Wed, 27 Mar 2013 20:33:23 +0100https://ask.sagemath.org/question/9948/finding-the-permutation-that-sorts-a-list/?answer=14698#post-id-14698Answer by vdelecroix for <p>Given a list (say, of numbers) <code>L</code>, the method <code>L.sort()</code> will put its elements in order. The function <code>sorted(L)</code> returns a new list with the elements of <code>L</code> in order. I would like a version of <code>sorted</code> that will not return the elements of <code>L</code> in sorted order, but rather, the <em>permutation</em> that puts them in sorted order. Does this exist in Sage? Thanks.</p>
https://ask.sagemath.org/question/9948/finding-the-permutation-that-sorts-a-list/?answer=14685#post-id-14685Hello,
It is possible to do
sage: L = [2,3,1,6,8,-3,9]
sage: Word(L).standard_permutation()
[3, 4, 2, 5, 6, 1, 7]
which is the inverse as the one given is the other answers... but then
sage: Word(L).standard_permutation().inverse()
[6, 3, 1, 2, 4, 5, 7]Thu, 28 Mar 2013 15:53:24 +0100https://ask.sagemath.org/question/9948/finding-the-permutation-that-sorts-a-list/?answer=14685#post-id-14685Comment by DSM for <p>Hello,</p>
<p>It is possible to do</p>
<pre><code>sage: L = [2,3,1,6,8,-3,9]
sage: Word(L).standard_permutation()
[3, 4, 2, 5, 6, 1, 7]
</code></pre>
<p>which is the inverse as the one given is the other answers... but then</p>
<pre><code>sage: Word(L).standard_permutation().inverse()
[6, 3, 1, 2, 4, 5, 7]
</code></pre>
https://ask.sagemath.org/question/9948/finding-the-permutation-that-sorts-a-list/?comment=18002#post-id-18002Oh, that's nice.Thu, 28 Mar 2013 16:23:31 +0100https://ask.sagemath.org/question/9948/finding-the-permutation-that-sorts-a-list/?comment=18002#post-id-18002Answer by John Palmieri for <p>Given a list (say, of numbers) <code>L</code>, the method <code>L.sort()</code> will put its elements in order. The function <code>sorted(L)</code> returns a new list with the elements of <code>L</code> in order. I would like a version of <code>sorted</code> that will not return the elements of <code>L</code> in sorted order, but rather, the <em>permutation</em> that puts them in sorted order. Does this exist in Sage? Thanks.</p>
https://ask.sagemath.org/question/9948/finding-the-permutation-that-sorts-a-list/?answer=14699#post-id-14699A slightly more compact version of DSM's answer:
sage: L = [2,3,1,6,8,-3,9]
sage: L2 = sorted(L)
sage: P = Permutation([list(L).index(x)+1 for x in L2])
Testing the answer:
sage: P
[6, 3, 1, 2, 4, 5, 7]
sage: P.action(L)
[-3, 1, 2, 3, 6, 8, 9]
I wouldn't be surprised if this were slower to execute.Wed, 27 Mar 2013 21:15:12 +0100https://ask.sagemath.org/question/9948/finding-the-permutation-that-sorts-a-list/?answer=14699#post-id-14699