Ask Your Question
1

Finding the permutation that sorts a list

asked 2013-03-27 13:44:08 -0500

Ed Scheinerman gravatar image

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 flag offensive close merge delete

3 answers

Sort by ยป oldest newest most voted
3

answered 2013-03-27 14:33:23 -0500

DSM gravatar image

updated 2013-03-27 16:38:34 -0500

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]
edit flag offensive delete link more
2

answered 2013-03-28 09:53:24 -0500

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]
edit flag offensive delete link more

Comments

Oh, that's nice.

DSM gravatar imageDSM ( 2013-03-28 10:23:31 -0500 )edit
1

answered 2013-03-27 15:15:12 -0500

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

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.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2013-03-27 13:44:08 -0500

Seen: 501 times

Last updated: Mar 28 '13