# 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.

edit retag close merge delete

Sort by ยป oldest newest most voted

IIUC, 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]

more

Hello,

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]

more

Oh, that's nice.

( 2013-03-28 16:23:31 +0100 )edit

A 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])


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.

more